想越狱的小杉

题目描述:

这次小杉来到了经典美剧《越狱》的场景里……

他被抓起来了（-.-干嘛幻想这么郁闷的场景……）。

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

在地道里，无数的管道路线困惑了他。（若对情节有任何疑问，请观看原剧） 

小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。

小房间编号为不超过N的正整数。

对于某个管道，小杉只能在人品不超过一定程度时通过。

小杉一开始在房间1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。

注意，小杉的人品在出发以后是不会改变的。

输入格式:

每组测试数据的第一行有一个正整数N ( 0 <= N <= 2000 ) 。

接下来若干行描述管道，每行三个正整数A,B,R(1<=A,B<=N)，表示A房间有一条到达B房间的管道，且小杉的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，即管道是单向的)

整个输入数据以一行0 0 0结束。

特别地，对于30%的数据，有N<=100。

输出格式:

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

样例输入:

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

样例输出:

30
25
25

提示:

对于样例数据：

小杉最多能够在人品为30的情况下到达小房间2(1->2)

小杉最多能够在人品为25的情况下到达小房间3(1->2->3)

小杉最多能够在人品为25的情况下到达小房间4(1->2->3->4)

图的存储方式：

存储1：
二维数组，注意存储空间

存储2：
struct data{
	int to, val;
};
vector< data > a[100001];

存储3：
struct node{
	int to,val,next;
}edge[ 400001 ];  //边的数量
int num, head[ 20001 ];   //顶点的数量
void add( int u, int v, int w ){
	edge[ ++num ].to = v;
	edge[ num ].val = w;
	edge[ num ].next = head[u];
	head[ u ] = num;
}

存储4：
和存储3原理一样，只是用多个独立的数组存储
int tot, to[ N ], val[ N ], _next[ N ], _head[ N ];
void add( int x, int y, int z ){
	to[ ++tot ] = y;
	val[ tot ] = z;
	_next[ tot ] = _head[x];
	_head[x] = tot;
}
存储3和存储4称为链式前向星，由某个顶点出发的边的顶点构成一条链，链的尾结点指针（next) 为0。