题目链接：https://codeforces.com/contest/1842/problem/D

借鉴：https://blog.csdn.net/Tanya_xiaomai/article/details/131393112

没看懂这个题

大意：丁真和他的n个动物朋友玩耍, 丁真非常喜欢他的1号朋友, 所以每次都要和1号朋友玩, 丁真不喜欢他的n号朋友, 所以丁真不和n号朋友玩
现在给出m个限制, 每个限制有u v w三个参数, 代表u号朋友和v号朋友不在一起的时间不超过w
(u和v同时都在和同时不在的时间不会被此条限制所影响)
丁真想尽可能用更多的时间和动物朋友们玩耍
请输出丁真最多能和动物朋友玩耍的时间和玩耍的次数
用二进制状态表示丁真和哪些动物朋友们玩耍, 并在同一行那一次输出玩耍了多久

其实是一个构造题，你需要构造一组满足最多玩耍时间的数据。满足约束

思路：首先1和n一定要在一个连通块中, 不一定需要1和n在一条边上但一定要在一个连通块中

因为无限的情况就是我们都一起玩就好了，然后单单不带n和它的连通块。因为只要有1就可以了。

相应的, 从1到n的最短路, 也就是此题中丁真最多能和动物朋友有玩的时间了。
这里就很抽象，最短路真是无奇不有。这里怎么考虑呢，因为只要我们存在绕路，就肯定会让某些点多进入一组游玩，这样就会破坏掉第三个的限制。
所以最短路就是最大满足的最大游玩时间。

每组数据通过贪心构造即可。
先构造最小的时间，然后在这个时间之前的我们都放进去就可以，每次游玩的时间，就是与上次游玩时间的之差。这里不难思考。

code：

void solve()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i!=j) a[i][j] = LNF;
			else a[i][j] = 0;
		}
	}
	int x,y,z;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		a[x][y] = a[y][x] = z;
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				a[i][j] = min(a[i][k]+a[k][j],a[i][j]);
	//首先可以确定的是1和n必须在一个连通中。
	//因为只有n存在绑定其他点，才可以利用n不属于S的限制从而有限。
	if(a[1][n]>=LNF/2){
		cout<<"inf"<<endl;
		return;
	}
	
	ll ans = a[1][n];
	vector<ll> ve,d(n+1);
	for(int i=1;i<=n;i++){
		d[i] = min(ans,a[i][n]);//能玩的最短的时间实际上就是组能玩的最短的时间。`
		ve.push_back(d[i]);
	}
	sort(ve.begin(),ve.end());//排个序去重，每次我们只取当前能玩的值减去上一轮，满足不一起的时间。
	// for(auto c: ve) cout<<c<<' ';cout<<endl;
	ve.erase(unique(ve.begin(),ve.end()),ve.end());
	cout<<ans<<' '<<ve.size()-1<<endl;
	ll ks = 0;
	for(int i=0;i<ve.size();i++){
		if(!ve[i]) continue;
		for(int j=1;j<=n;j++){
			cout<<(d[j]>=ve[i]);//可以满足的加进去
		}
		cout<<' '<<ve[i]-ks<<endl;//之后的时间就是当前可以玩的减去之前不在一起的时间
		ks = ve[i];
	}
}