传送门


题意：求出最短路树的方案数和方案情况（1表示使用这条边，0表示未用到）。

这道题的思路很巧妙！！题上定义的代价为每个点到起始点（1）的距离之和，很容易想到最短路，我们可以用BFS，DIJ，SPFA求解。每一种情况都是以 1 为根节点的一棵树，我们要怎样才能得到更多的情况呢，如果存在两点 a 和 b。 a 和 b 有一条边相连，并且 dis[ a ] + 1 = dis [ b ] ，我们可以建一条边 b → a ，然后不断跑 DFS 就可以得到答案。

为什么我们建边时是反着建边呢？而不是 a → b 呢？因为每种情况是一颗树，每个结点的前驱结点只有一个，如果我们 按照 a → b
建边，我们就无法 DFS 获得答案。我们DFS时按照结点来递归。

坑点：尽量不要定义临时变量，居然这次还MLE了。。。。

附上代码：

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<list>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const int INF=0x3f3f3f3f;

int n,m,k;

struct node
{
    int e;
    int sub;
    int p;
}load[400005];
int head[200005],sign;

void add_edge(int s,int e,int sub)
{
    load[++sign]=node{e,sub,head[s]};
    head[s]=sign;
}

int depth[200005];
vector<int>edge[200005];
vector<string>ans;
string state;

void bfs()///求最短路
{
    queue<int>q;
    int vis[200005];
    memset(vis,0,sizeof(vis));
    vis[1]=1;
    q.push(1);
    int s;
    while(!q.empty())
    {
        s=q.front();
        q.pop();
        for(int i=head[s];i!=-1;i=load[i].p)
        {
            int e=load[i].e;
            if(!vis[e])
            {
                vis[e]=1;
                depth[e]=depth[s]+1;
                q.push(e);
            }
        }
    }
}
void dfs(int s)
{
    if(ans.size()>=k)
        return ;
    if(s>n)///结点大于n结束
    {
        ans.push_back(state);
        return ;
    }
    int d=edge[s].size();
    for(int i=0;i<d;i++)
    {
        int sub=edge[s][i];
        state[sub-1]='1';
        dfs(s+1);
        state[sub-1]='0';
    }
}

void init()
{
    sign=0;
    memset(head,-1,sizeof(head));
    depth[1]=0;
}

int main()
{
    int s,e;
    scanf("%d %d %d",&n,&m,&k);
    init();
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d",&s,&e);
        add_edge(s,e,i);
        add_edge(e,s,i);
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=-1;j=load[j].p)
        {
            s=i;
            e=load[j].e;
            if(depth[s]+1==depth[e])///放入e和前驱结点s边的编号
                edge[e].push_back(load[j].sub);
        }
    }
    state=string(m,'0');
    dfs(2);///递归结点
    int d=ans.size();
    printf("%d\n",ans.size());
    while(d--)
        cout<<ans[d]<<endl;
    return 0;
}