Universal Online Judge
UOJ
时间限制:1 s
空间限制:32 MB
#499. 牛跑步
统计BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘,
然后走回牛棚.
BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路,
每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高
度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘.
很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K
<= 100)条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经.
请帮助BESSIE找出这K条最短路经的长度.你的程序需要读入农场的地图, 一些从X_i到Y_i
的路经和它们的长度(X_i, Y_i, D_i). 所有(X_i, Y_i, D_i)满足(1 <= Y_i < X_i;
Y_i < X_i <= N, 1 <= D_i <= 1,000,000).
题名: cowjog
输入格式:
* 第1行: 3个数: N, M, 和K
* 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.
样例输入 (cowjog.in):
5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1
输出格式:
* 第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.如果多条路经有
同样的长度,请注意将这些长度逐一列出.
样例输出 (cowjog.out):
1
2
2
3
6
7
-1
输出解释:
路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),
(5-4-3-2-1).
[title]Source[/title]
[link=exerciseproblems?source=usaco]usaco[/link]