#P2901. [USACO08MAR] Cow Jogging G

    ID: 1838 Type: RemoteJudge 1000ms 125MiB Tried: 1 Accepted: 1 Difficulty: 6 Uploaded By: Tags>动态规划dp广度优先搜索BFS递推USACO2008

[USACO08MAR] Cow Jogging G

题目描述

贝西终于尝到了懒惰的后果,决定每周从谷仓到池塘慢跑几次来健身。当然,她不想跑得太累,所以她只打算从谷仓慢跑下山到池塘,然后悠闲地散步回谷仓。

同时,贝西不想跑得太远,所以她只想沿着通向池塘的最短路径跑步。一共有 MM 条道路,其中每一条都连接了两个牧场。这些牧场从 11NN 编号,如果 X>YX>Y,则说明牧场 XX 的地势高于牧场 YY,即下坡的道路是从 XX 通向 YY 的,NN 为贝西所在的牛棚(最高点),11 为池塘(最低点)。

然而,一周之后,贝西开始对单调的路线感到厌烦,她希望可以跑不同的路线。比如说,她希望能有 KK 种不同的路线。同时,为了避免跑得太累,她希望这 KK 条路线是从牛棚到池塘的路线中最短的 KK 条。如果两条路线包含的道路组成的序列不同,则这两条路线被认为是不同的。

请帮助贝西算算她的训练强度,即将牧场网络里最短的 KK 条路径的长度分别算出来。你将会被提供一份牧场间路线的列表,每条道路用 (Xi,Yi,Di)(X_i, Y_i, D_i) 表示,意为从 XiX_iYiY_i 有一条长度为 DiD_i 的下坡道路。

输入格式

第一行三个用空格分开的整数 N,M,KN,M,K,其中 。

第二行到第 M+1M+1 行每行有三个用空格分开的整数 Xi,Yi,DiX_i,Y_i,D_i,描述一条下坡的道路。

输出格式

KK 行,在第 ii 行输出第 ii 短的路线长度,如果不存在则输出 1-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 

提示

样例 1 解释

这些路线分别为 (5-1)、(5-3-1)、(5-2-1)、(5-3-2-1)、(5-4-3-1) 和 (5-4-3-2-1)。

数据规模与约定

对于全部的测试点,保证 1N1,0001 \le N \le 1,0001M1×1041 \le M \le 1\times10^41K1001 \le K \le 1001Yi<XiN1 \le Y_i < X_i\le N1Di1×1061 \le D_i \le 1\times 10^6