1 条题解
-
0
/* 判断是否有合法解,最短路和最长路都行,这里采用最长路 P a b c: s[ b ]-s[ a ]<=c -> s[ b ]-c<=s[a] - > G[ b ].push_back({a,-c}); s[ b ]-s[ a ]>=c -> s[ a ]+c<=s[ b ] -> G[a].push_back({b,c}); V a b: s[ b ]-s[ a ]>=1 -> s[ a ]+1<=s[ b ] -> G[a].push_back({b,1})。 */ #include<bits/stdc++.h> using namespace std; constexpr int N=1010; vector< pair<int,int> > G[N]; int n,st,ed,d[N],dd[N];bool v[N]; int spfa() { memset(d,0,sizeof(d));memset(dd,0,sizeof(dd)); memset(v,0,sizeof(v)); queue<int>q; for(int i=st;i<=ed;i++)q.push(i),v[i]=1; d[st]=0; while(!q.empty()) { int x=q.front(); q.pop();v[x]=0; for(auto i:G[x]) { int y=i.first,w=i.second; if(d[y]<d[x]+w) { d[y]=d[x]+w; dd[y]=dd[x]+1;if(dd[y]>n)return 0; if(v[y]==0) q.push(y),v[y]=1; } } } return 1; } int main() { int m; while(scanf("%d",&n) && n) { scanf("%d",&m); memset(G ,0,sizeof(G)); st=n+1;ed=0; for(int i=1,a,b,c;i<=m;i++) { char op[5];scanf("%s%d%d",op,&a,&b); if(op[0]=='P') { scanf("%d",&c); G[ b ].push_back({a,-c}); G[a].push_back({b,c}); } else G[a].push_back({b,1}); st=min(st,min(a,b)); ed=max(ed,max(a,b)); } if( !spfa() ) printf("Reliable\n"); else printf("Unreliable\n"); } return 0; }
- 1
信息
- ID
- 702
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 9
- 标签
- 递交数
- 94
- 已通过
- 9
- 上传者