[Codeforces 1005F]Berland and the Shortest Paths(最短路树+dfs)

题面

题意：给你一个无向图，1为起点，求生成树让起点到其他个点的距离最小，距离最小的生成树可能有多个。给定k，如果方案数比k小就输出全部方案，否则输出k种方案。

分析

先跑最短路，对于每个点找到它在最短路树上可能的父亲.即对于\((x,y) \in E,dist(y)=dist(x)+len(x,y)\)。那么y在最短路上可能的父亲就是x.说“可能”是因为最短路树可能不唯一。

然后dfs枚举每个点选哪个父亲，输出答案即可。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#define maxn 300000

#define maxm 300000

#define INF 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

int n,m,k;

struct edge {

	int from;

	int to;

	int next;

	int id;

	int type;

} E[maxm*2+5];

int head[maxn+5];

int esz=1;

void add_edge(int u,int v,int id) {

	esz++;

	E[esz].from=u;

	E[esz].to=v;

	E[esz].next=head[u];

	E[esz].id=id;

	head[u]=esz;

}

struct node {

	int id;

	ll dist;

	node() {

	}

	node(int _id,ll _dist) {

		id=_id;

		dist=_dist;

	}

	friend bool operator < (node p,node q) {

		return p.dist>q.dist;

	}

};

int pre[maxn+5];

bool vis[maxn+5];

ll dist[maxn+5];

void dijkstra(int s) {

	priority_queue<node>q;

	memset(vis,0,sizeof(vis));

	memset(dist,0x3f,sizeof(dist));

	dist[s]=0;

	q.push(node(s,0));

	while(!q.empty()) {

		int x=q.top().id;

		q.pop();

		if(vis[x]) continue;

		vis[x]=1;

		for(int i=head[x]; i; i=E[i].next) {

			int y=E[i].to;

			if(dist[y]>dist[x]+1) {

				dist[y]=dist[x]+1;

				pre[y]=i;

				if(!vis[y]) q.push(node(y,dist[y]));

			}

		}

	}

//	for(int i=1; i<=n; i++) {

//		if(pre[i]) E[pre[i]].type=E[pre[i]^1].type=1;

//	}

}

vector<int>T[maxn+5];

int cnt=0;

vector<string>ans;

string now;

void dfs(int x){//搜索每个点的前驱

	if(ans.size()>=k) return;

	if(x>n){

		ans.push_back(now);

		return;

	}

	for(int i=0;i<T[x].size();i++){

		//枚举选哪个前驱

//		printf("db: %d\n",T[x][i]);

		now[T[x][i]-1]='1';

		dfs(x+1);

		now[T[x][i]-1]='0';

	}

}

int main() {

	int u,v;

	scanf("%d %d %d",&n,&m,&k);

	for(int i=1;i<=m;i++){

		scanf("%d %d",&u,&v);

		add_edge(u,v,i);

		add_edge(v,u,i);

	}

	dijkstra(1);

	for(int i=2;i<=esz;i++){

		int x=E[i].from;

		int y=E[i].to;

		if(dist[y]==dist[x]+1){

			T[y].push_back(E[i].id);

			//找每个点的前驱

			//注意不是x而是id

		}

	}

	now.resize(m);

	for(int i=0;i<m;i++) now[i]='0';

	dfs(2);//从2开始搜索前驱

	printf("%d\n",ans.size());

	for(int i=0;i<ans.size();i++){

//		for(int j=0;j<ans[i].length();j++) putchar(ans[i][j]);

		cout<<ans[i];

		putchar('\n');

	}

}