小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。 小房间编号为不超过N的正整数。 对于某个管道，小杉只能在人品不超过一定程度时通过。 小杉一开始在房间1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。 注意，小杉的人品在出发以后是不会改变的。
每组测试数据的 第一行有一个正整数N(1<=N<=2000)。 接下来若干行描述管道，每行三个正整数A,B,R(1<=A,B<=N)，表示A房间有一条到达B房间的管道，且小杉的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，即管道是单向的) 整个输入数据以一行0 0 0结束 特别地，对于30%的数据，有N<=100
对每组测试数据输出N-1行，分别表示对于2到N号的小房间，小杉最多能够以人品多少的状态到达。
SPFA变式…
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> #define maxn 2000+100 #define INF 1000000000-1 using namespace std; int n,a,b,r; int edge[maxn][maxn],d[maxn],cnt[maxn]; bool vis[maxn],flag=true; queue<int> q; //d[i]代表从出发点到i点的最大RP //更新d[i]当d[cur]>d[i] 且edge[cur][i]>d[i] //d[i]初始为0 void spfa(){ q.push(1); d[1]=INF; while(!q.empty()&&flag){ int cur=q.front(); q.pop(); vis[cur]=false; for(int i=1;i<=n;i++){ if(edge[cur][i]!=-1){ if(d[cur]>d[i]&&edge[cur][i]>d[i]){ d[i]=min(d[cur],edge[cur][i]); if(!vis[i]){ q.push(i); cnt[i]++; if(cnt[i]>n){ flag=false; break; } } } } } } return; } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); memset(edge,-1,sizeof(edge)); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); memset(d,0,sizeof(d)); while(scanf("%d%d%d",&a,&b,&r)!=EOF){ if(a==b&&b==r&&a==0) break; edge[a][b]=r; } spfa(); for(int i=2;i<=n;i++) printf("%d\n",d[i]); return 0; }转载于:https://www.cnblogs.com/leotan0321/p/6081402.html
