CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) D. Tenzing and His Animal Friends

题面是真的抽象，翻译为人话之后大概就是，对于每个选择的集合当中，1必须选，n一定不能选，每个限制条件的意思是如果u和v不在一个集合里则最能玩y时间，则u或v独自玩最多玩y时间

如果在同一集合则可以玩无限时间

因此如果n和1不连通的话则一定为inf,否则的话就一定有限制，因为n一定不能选，则和n相连的必定受限制，因此这些限制一直传递，如果传不到1则可以无限玩

转换之后就是一个最短路问题，求n到i的最短路，最后d[1]就是能玩的最大时间限制

因为根据贪心的思想可得，我们让所有有限制的动物处于同一集合当中这样就可以解除限制，但是由于n一定不在集合中，因此集合当中玩的最大时间实际上就是和n的限制的最小数，不能超过这个限制，例如3->2->5,如果1,3,2一起玩的话则最多玩1分钟，1，3，2实际上是受2的限制，1,3一起玩的话本来最多玩2分钟但是因为之前3已经玩了1分钟因此也是1分钟，此时受3的限制

每次迭代，先求出当前集合里的最小时间，则目前这个集合最多能玩的就是这个时间，然后这个集合里面所有等于最小时间的都不能继续玩了，即被淘汰了

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N=110;
const ll INF=1e18+20;
ll d[N];//记录n到i的最短路
int a[N][N];
bool st[N];
int n,m;
vector<string> s;
vector<ll> min_res;
void dijstra(){
	d[n]=0;
	for(int i=0;i<n-1;i++){
		int t=-1;
		for(int j=1;j<=n;j++)
		if(!st[j]&&(t==-1||d[t]>d[j]))
		t=j;
		st[t]=true;
		for(int j=1;j<=n;j++){
			if(a[t][j]!=0x3f3f3f3f)//如果t和j不连通的话就不更新
			d[j]=min(d[j],d[t]+a[t][j]);
		}
	}
}
ll get_min(){
	ll cnt=INF;
	for(int i=1;i<=n;i++){
		if(d[i]>0)//求的是还可以一起玩的
		cnt=min(cnt,d[i]);
	}
	return cnt;
} 
void solve(){
	cin>>n>>m;
	memset(a,0x3f,sizeof a);
	memset(st,0,sizeof st);
	for(int i=1;i<=n;i++) d[i]=INF;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		a[x][y]=a[y][x]=min(a[x][y],z);
	}
	dijstra();
	if(d[1]==INF){//如果1和n不连通的话就可以无限玩
		puts("inf");
		return;
	}
	ll res=d[1];
	string temp;
	while(d[1]>0){
		ll cnt=get_min();//求出现在集合当中的最小值，从1开始求
		temp.clear();
		min_res.push_back(cnt);
		for(int i=1;i<=n;i++){
			if(d[i]>0){//集合里面每个数字都减去该最小值得到还可以玩的时间
				d[i]-=cnt;
				temp+='1';
			}
			else{
				temp+='0';
			}
		}
		s.push_back(temp);
	}
	cout<<res<<" "<<s.size()<<endl;
	for(int i=0;i<s.size();i++){
		cout<<s[i]<<" "<<min_res[i]<<endl;
	}
} 
int main(){
		solve();
}