题目链接：点击这里

题目大意：
给你一张图输出 k k k （没有 k k k 个就有多少种方案就输出多少种方案）个图的最短路径树，每次输出一个 01 01 01 串从左往右第 i i i 位 0 , 1 0,1 0,1 分别表示第 i i i 条边是否被选择

题目分析：
因为这个题的边权是 1 1 1 所以可以用 b f s bfs bfs 代替 d i j k s t r a dijkstra dijkstra 算法，这样时间复杂度能生一个 l o g log log ，这个题只需要在维护最短路径树的同时维护有哪些最短路径树上的边指向了当前节点，输出的时候只需要 d f s dfs dfs 扫一遍就可以了

具体细节见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>
#define ll long long
#define inf 0x3f3f3f3f
#define int ll
using namespace std;
int read()
{
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 3e5+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct Edge {
	int nxt,to,id;
}edge[maxn<<1];
int n,m,k,head[maxn],cnt,dis[maxn];
bool vis[maxn],used[maxn];
vector<int>v[maxn];
void addedge(int from,int to,int id)
{
	edge[++cnt].nxt = head[from];
	edge[cnt].to = to;
	edge[cnt].id = id;
	head[from] = cnt;
}
void bfs(int u)
{
	queue<int>qu;
	memset(dis,inf,sizeof(dis));
	dis[u] = 0;
	qu.push(u);
	while(!qu.empty())
	{
		int h = qu.front();
		qu.pop();
		if(vis[h]) continue;
		vis[h] = true;
		for(int i = head[h];i;i = edge[i].nxt)
		{
			int to = edge[i].to;
			if(dis[to] == dis[h]+1)
				v[to].push_back(edge[i].id); 
			if(dis[to] > dis[h]+1)
			{
				v[to].clear();
				v[to].push_back(edge[i].id); 
				dis[to] = dis[h]+1;
				qu.push(to);
			}
		}
	}
}
int num;
void dfs(int dep) //输出方案
{
	if(dep == n+1)
	{
		for(int i = 1;i <= m;i++)
			printf("%d",used[i]);
		puts("");
		++num;
		if(num == k) exit(0);//输出够了直接结束
		return ;
	}
	for(auto to : v[dep])
	{
		used[to] = 1;
		dfs(dep+1);
		used[to] = 0;
	}
}
signed main()
{
	n = read(),m = read(),k = read();
	for(int i = 1;i <= m;i++)
	{
		int from = read(),to = read();
		addedge(from,to,i);
		addedge(to,from,i);
	}
	bfs(1);
	int sum = 1;
	for(int i = 2;i <= n;i++)
	{
		sum *= v[i].size();
		if(sum >= k) break;
	}
	k = min(k,sum);
	printf("%lld\n",k);
	dfs(2);
	return 0;
}