题面是真的抽象,翻译为人话之后大概就是,对于每个选择的集合当中,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();
}