网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
旅行
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | travela.in | 输出文件 | travela.out |
【问题描述】
一天,TZD想从0号村庄游历到n-1号村庄,这n个村庄由m条有向路连接,某两个村庄间可能有多条路相连。
当他在处于同一个强连通分支中的两个村庄间游历时,他可以租辆自行车来骑着,否则的话,就只能步行了。说的再详细点,对于从村庄a到村庄b的每一条路,如果这两个村庄处在同一个强连通分支中,(这意味着你可以从a到达b,也可以从b到达a)那么你可以租一辆自行车来骑行,所用时间为time[a][b]分钟,否则你必须步行通过,所用时间为2*time[a][b]分钟。
TZD想尽快到达目的地,他希望在此过程中步行的路不超过k条。现在你需要为他计算出:在满足步行的路不超过k条的情况下,到达目的地所用的最短时间。
【输入格式】
输入文件有一组或多组数据每一组数据的第一行有三个整数:n,m,k,含义如上所述(1<=n<=100, 0<=m<=100 000, 0<=k<=10)。
接下来有m行,每行有3个整数a,b,time[a][b],表示从村庄a至村庄b有一条路,骑自行车需time[a][b]分钟,而步行则需2*time[a][b]分钟。(0<=a,b<=n-1)
输入文件以单独的一行3个0表示结束。
对于每一组测试数据,在一行输出其答案,如果TZD无法在步行不超过k条路的情况下到达目的地,则输出-1。
【样例】
travela.in
5 6 3
0 1 1
0 2 2
2 1 1
1 3 3
3 1 3
3 4 2
0 0 0
travela.out
9