其实是一道裸题，如果没学过最短路树的话会比较难做，要想很久想到关键性质才能做出来。
最短路树顾名思义，就是从一个图中生成出来一棵树，使得每个顶点到root的距离是单源最短路。如果有这样的树的话，那可见这样的树是符合题意的。
怎么生成这样的树呢？关键在于记录前驱father，一个距离root最短路是6的点必定从一个距离root最短路是5的点到达（这两个点之间一定会有一条边）。所以我们对于所有顶点 2-n，每个顶点u我们找dis[u] = dis[v]+1的情况，这样的话v就是u的前驱。若v，u之间有一条边，那u到root的最短路就解决了【因为如果v到root的最短路不变，那u也不变】，原问题就变成了子问题，这就是这么建树 正确性的理解。
所有合法前驱记录完后，我们dfs下枚举所有前驱就可以了。【最多能生成father[2].size() * father[3].size() * ... * father[n].size()个合法答案】
1 1 #include<iostream> 2 2 #include<vector> 3 3 #include<map> 4 4 #include<cstring> 5 5 #include<queue> 6 6 using namespace std; 7 7 8 8 char comp[200005]; 9 9 vector< pair<int,int> > edge[200005]; 1010 vector<int> father[200005]; 1111 vector<string> ans; 1212 int dis[200005],n,k; 1313 queue< pair<int,int> > q; 1414 1515 void dfs(int u){ 1616 if( ans.size()>=k ) return; 1717 if(u==n+1) { ans.push_back(comp+1); return;}//建完了 1818 for(int i=0;i<father[u].size();i++){ 1919 comp[ father[u][i] ] = '1';//从众多前驱中挑一个 2020 dfs(u+1); 2121 comp[ father[u][i] ] = '0'; 2222 } 2323 } 2424 2525 int main(){ 2626 int m; cin>>n>>m>>k; 2727 for(int i=1;i<=m;i++){ 2828 int u,v; scanf("%d %d",&u,&v); 2929 edge[u].push_back( make_pair(v,i) ); 3030 edge[v].push_back( make_pair(u,i) );//建两条边 3131 } 3232 3333 3434 memset(dis,-1,sizeof(dis)); 3535 for (int i = 1; i <= m; i++) comp[i] = '0'; 3636 //维护出dis数组 3737 q.push( make_pair(1,0) ); dis[1]=0; 3838 while(!q.empty()){ 3939 pair<int,int> pa = q.front(); q.pop(); 4040 int u=pa.first,d=pa.second; 4141 for(int i=0;i<edge[u].size();i++){ 4242 int v=edge[u][i].first; 4343 if( dis[v]==-1 ) { 4444 dis[v]=d+1; 4545 q.push( make_pair(v,d+1) ); 4646 } 4747 } 4848 } 4949 //找最短路数里每个顶点的前驱 5050 for(int i=2;i<=n;i++){ 5151 for(int j=0;j<edge[i].size();j++){ 5252 if( dis[i]==dis[ edge[i][j].first ]+1 ) father[i].push_back( edge[i][j].second ); 5353 } 5454 } 5555 5656 dfs(2);//从2开始建树 5757 if(ans.size()>=k){ 5858 cout<<k<<endl; 5959 for(int i=0;i<k;i++) cout<<ans[i]<<endl; 6060 } 6161 else{ 6262 cout<<ans.size()<<endl; 6363 for(int i=0;i<ans.size();i++) cout<<ans[i]<<endl; 6464 } 6565 6666 6767 return 0; 6868 }