|
|
|
|
背景 Background |
|
|
|
这次小杉来到了经典美剧《越狱》的场景里……
他被抓起来了（-.-干嘛幻想这么郁闷的场景……）。
小杉身为新一代的Scofield，在挖了半个月之后终于挖通牢房里的地道。
在地道里，无数的管道路线困惑了他。
（若对情节有任何疑问，请观看原剧）
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
小杉看了看自己的纹身，明白了整个管道网是由N个小房间和若干小房间之间的单向的管道组成的。
小房间编号为不超过N的正整数。
对于某个管道，小杉只能在人品不超过一定程度时通过。
小杉一开始在房间1，现在小杉想知道，每个小房间他最多能够以人品多少的状态到达。
注意，小杉的人品在出发以后是不会改变的。 |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
每组测试数据的
第一行有一个正整数N(1<=N<=2000)。
接下来若干行描述管道，每行三个正整数A,B,R(1<=A,B<=N)，表示A房间有一条到达B房间的管道，且小杉的人品不超过R时可以通过（注意从B房间不可由此管道到达A房间，即管道是单向的)
整个输入数据以一行0 0 0结束
特别地，对于30%的数据，有N<=100
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
对每组测试数据输出N-1行，分别表示对于2到N号的小房间，小杉最多能够以人品多少的状态到达。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
每个测试点1s |
|
|
|
|
|
|
|
注释 Hint |
|
|
|
对于样例数据：
小杉最多能够在人品为30的情况下到达小房间2(1->2)
小杉最多能够在人品为25的情况下到达小房间3(1->2->3)
小杉最多能够在人品为25的情况下到达小房间4(1->2->3->4) |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1391 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
