OI题库

【题目描述】

约翰正在制造一台新型的挤奶机，但它不希望别人知道。他希望尽可能久地隐藏这个秘密。他把挤奶机藏在他的农场里，使它不被发现。在挤奶机制造的过程中，它需要去挤奶机所在的地方T（1<=T<=200）次。他的农场里有秘密的地道，但约翰只在返回的时候用它。

农场被划分成N（2<=N<=200）块区域，用1到N标号。这些区域被P（1<=P<=40000）条双向道路连接。每条路有一个小于10^6的长度L，两块区域之间可能有多条道路连接。

为了减少被发现的可能，约翰不会两次经过农场上的任何一条道路。当然了，他希望走最短的路。

请帮助约翰寻找这T次从仓库走到挤奶机所在地的路线。仓库是区域1，挤奶机所在地是区域N。我们现在要求的是约翰经过的这些道路中最长的路的长度最小是多少，当然他不能重复走某一条路。请注意，我们要求的不是最短的总路程长度，而是所经过的直接连接两个区域的道路中最长的道路的最小长度。

数据保证约翰可以找到T条没有重复的从仓库到挤奶机所在区域的路。

【输入格式】

第1行是3个整数N,P和T，用空格隔开。

第2到P+1行，每行包括3个整数，Ai,Bi,Li，表示区域Ai,Bi之间有一条长度为Li的道路。

【输出格式】

输出只有一行，包含一个整数，即约翰经过的这些道路中最长的路的最小长度。

【样例输入】

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.

【来源】

USACO FEB05 Silver

Vladimir Novakovski, 2003

Translate by: 庄乐