题目描述：给出一个无向图，找出使每个点离1号距离都有最小值时边的k个选择方案。
题解：
先跑bfs求最短路，然后总方案数*=节点a与深度小于a的点相连边数。
最后枚举每个点连哪条边。
代码：
#include#include #include #include using namespace std;#define N 200050int n,m,k,hed[N],cnt;struct EG{ int to,id,nxt;}e[2*N];void ae(int f,int t,int v){ e[++cnt].to = t; e[cnt].id = v; e[cnt].nxt = hed[f]; hed[f] = cnt;}int dep[N];bool vis[N];void dij(){ memset(dep,0x3f,sizeof(dep)); dep[1]=0; queue q; q.push(1); vis[1]=1; while(!q.empty()) { int u = q.front(); q.pop(); for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; if(!vis[to]) { vis[to]=1; dep[to]=dep[u]+1; q.push(to); } } }}int f[N];int ans[N],sum=1;void dfs(int i){ if(i==n+1) { for(int i=1;i<=m;i++)printf("%d",ans[i]); printf("\n"); sum--; if(!sum)exit(0); } for(int j=hed[i];j;j=e[j].nxt) { int to = e[j].to; if(dep[to]!=dep[i]-1)continue; ans[e[j].id]=1; dfs(i+1); ans[e[j].id]=0; }}int main(){ scanf("%d%d%d",&n,&m,&k); for(int f,t,i=1;i<=m;i++) { scanf("%d%d",&f,&t); ae(f,t,i),ae(t,f,i); } dij(); for(int i=2;i<=n;i++) { int cnt = 0; for(int j=hed[i];j;j=e[j].nxt) { int to = e[j].to; if(dep[to]==dep[i]-1)cnt++; } sum *= cnt; if(sum>=k) { sum=k; break; } } printf("%d\n",sum); dfs(2); return 0;}