描述 Description
小杉看了看自己的纹身，明白了整个管道网是由 N 个小房间和若干小房间之间的单向的管道组成的。
小房间编号为不超过 N 的正整数。
对于某个管道，小杉只能在人品不超过一定程度时通过。
小杉一开始在房间 1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。
注意，小杉的人品在出发以后是不会改变的。
输入格式 InputFormat
每组测试数据的第一行有一个正整数 N(1<=N<=2000)。
接下来若干行描述管道，每行三个正整数 A,B,R(1<=A,B<=N)，表示 A 房间有一条到达 B 房间的管道，且小杉的人品不超过 R 时可以通过（注意从 B 房间不可由此管道到达 A 房间，即管道是单向的)
整个输入数据以一行 0 0 0 结束
特别地，对于 30% 的数据，有 N<=100
输出格式 OutputFormat
对每组测试数据输出 N-1 行，分别表示对于 2 到 N 号的小房间，小杉最多能够以人品多少的状态到达。
样例输入 SampleInput
4
1 2 30
1 3 20
2 3 25
3 4 30
2 4 20
0 0 0
样例输出 SampleOutput
30
25
25
代码 Code
spfa, 每次取来时房间及管道的最小值，起点的 rp 设为 max 即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf=0x7fffffff/27.11;
const int maxn=2005;
int i,j,t,n,m,l,r,k,z,y,x;
struct edge
{
int to,next,val;
}e[maxn*maxn];
int dis[maxn],head[maxn];
bool used[maxn];
deque <int> q;
int cnt;
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;e[cnt].next=head[u];e[cnt].val=w;
head[u]=cnt;
}
inline void spfa(int s)
{
int i,j,t,k,u,v,w;
memset(used,false,sizeof(used));
memset(dis,0,sizeof(dis));
while (!q.empty()) q.pop_front();
q.push_back(s);used[s]=true;
for (i=head[s];i;i=e[i].next) dis[s]=max(dis[s],e[i].val);
while (!q.empty())
{
u=q.front();q.pop_front();used[u]=false;
for (i=head[u];i;i=e[i].next)
{
v=e[i].to;w=e[i].val;
if (dis[v]<min(dis[u],w))
{
dis[v]=min(dis[u],w);
if (!used[v])
{
used[v]=true;
if (!q.empty() && dis[q.front()]<dis[v]) q.push_front(v);
else q.push_back(v);
}
}
}
}
}
int main()
{
scanf("%d",&n);
cnt=0;
scanf("%d%d%d",&x,&y,&z);
while (x!=0 && y!=0 && z!=0)
{
ins(x,y,z);
scanf("%d%d%d",&x,&y,&z);
}
spfa(1);
for (i=2;i<=n;i++) printf("%d\n",dis[i]);
return 0;
}