牛跑步

ID: 3833

Type: RemoteJudge

1000ms

256MiB

Difficulty: (None)

Uploaded By:

No submission language available for this problem.

题目描述

BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BES

SIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1

<= N 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).

* 第1行: 3个数: N, M, 和K

* 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.

* 第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.

如果多条路经有同样的长度,请注意将这些长度逐一列出.

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 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).