P1605【2012 Summer Test2】嵩嵩运货 | |
|
問題説明
受何老板之托,嵩嵩在美国为何老板采购的若干吨货物。这批货物已通过水路运送到了我国某沿海城市,现在需要通过公路将这些货物运送到何老板家。嵩嵩的地图上有N(2 <= N <= 200) 座城市,编号1到N,嵩嵩在1号城市,何老板的家在N号城市。这N座城市间有P(1 <= P <= 40,000) 条双向通行的道路相连,每条道路长度不超过1,000,000。两座城市间可能有多条道路相连。
嵩嵩雇了T(1 <= T <= 200)辆卡车运送这批货物。为了避免被人发现或引起别人的注意,嵩嵩安排这T辆车选择不同的道路行驶,也就是同一条道路不会被走两次。
请帮助嵩嵩安排这T辆车的线路,使得走过的最长的一条道路尽可能短。
嵩嵩向你保证在不走重复道路的情况下,一定能够把T车货物运到目的地。
注意:题目中描述的“道路”相当于图论中的“边”。
入力形式
第一行包括三个空格间隔的整数N,P,T。
接下来P行,每行有三个空格间隔的整数A,B,C。表示城市A、B间有条长度为C的道路。
出力形式
一整数,表示经过的最长道路最短可能的长度。
サンプル入力
7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
サンプル出力
5
ヒント
样例说明:
两次行走的线路分别是1 - 2 - 3 - 7和1 - 6 - 7. 其中最长一条道路的长度是5。
也就是说不可能找到两条可行的线路,使得其中最长的一条道路的长度比5更小。
番外篇:NKOJ3000