比赛场次 142
比赛名称 20120703
比赛状态 已结束比赛成绩
开始时间 2012-07-03 08:00:00
结束时间 2012-07-03 12:00:00
开放分组 全部用户
注释介绍 2012暑假培训A班
题目名称 旅行
输入输出 travela.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
GravatarIMSL77 AAAAAAAAAA 0.033 s 1.43 MiB 100
Gravatarisabella AAAAAAAAAA 0.053 s 0.21 MiB 100
GravatarCzb。 AAAAAAAAWW 0.146 s 3.36 MiB 80
GravatarCitron酱 AAAAAAWAWW 0.183 s 3.21 MiB 70
Gravatarwo shi 刘畅 AAAAWWAWWW 0.032 s 15.67 MiB 50
Gravatarczp AAAWWWAWWW 0.029 s 13.40 MiB 40
Gravatarfuhao AWWWWWAWWW 0.012 s 0.22 MiB 20
GravatarZhouHang AWWWWWAWWW 0.018 s 11.20 MiB 20
GravatarTBK AWWWWWAWWW 0.018 s 87.16 MiB 20
Gravatarzhangchi AWWWWWAWWW 0.175 s 4.18 MiB 20
Gravatarkaaala AWAWWTWTWT 3.017 s 3.29 MiB 20
GravatarMakazeu WWWWWWAWWW 0.006 s 3.33 MiB 10
GravatarCC RRRRRRRRRR 0.002 s 36.31 MiB 0
Gravatar王者自由 WWWWWWWWWW 0.212 s 2.01 MiB 0

旅行

★   输入文件:travela.in   输出文件:travela.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述

一天,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