题目描述

这次小杉来到了经典美剧《越狱》的场景里……他被抓起来了（-.-干嘛幻想这么郁闷的场景……）。

小杉身为新一代的Scofield，在挖了半个月之后终于挖通牢房里的地道。

在地道里，无数的管道路线困惑了他。

小杉看了看自己的纹身，明白了整个管道网是由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，对于100%的数据，有N<=2000.

输出

    对每组测试数据输出N-1行，分别表示对于2到N号的小房间，小杉最多能够以人品多少的状态到达（到达不了为0）。

样例输入

4
1 2 30
1 3 20
2 3 25
3 4 30
2 4 20
0 0 0

样例输出

30
25
25

提示

来源

#include<bits/stdc++.h>
using namespace std;
struct edge{int v,w;bool operator<(edge a)const{return w<a.w;}
}now,temp;
int dis[10005],n,m;
bool vis[10005];
vector<edge>a[10005];
void dijkstra(){memset(dis,0,sizeof(dis));memset(vis,0,sizeof(vis));dis[1]=0x3f3f3f3f;priority_queue<edge>q;q.push({1,dis[1]});while(!q.empty()){now=q.top();q.pop();if(vis[now.v]) continue;vis[now.v]=1;int len=a[now.v].size();for(int i=0;i<len;i++){temp=a[now.v][i];if(min(dis[now.v],temp.w)>dis[temp.v]){dis[temp.v]=min(dis[now.v],temp.w);q.push({temp.v,dis[temp.v]});}}}}
int main(){cin>>n;int u,v,w;while(1){cin>>u>>v>>w;if(u==0&&w==0&&v==0) break;a[u].push_back({v,w});}dijkstra();for(int i=2;i<=n;i++){cout<<dis[i]<<endl;}return 0;}

图论-最短路