#2428. 【奶牛派对】最短路径

【奶牛派对】最短路径

题目描述

母牛从NN 个农场中的任一个去参加盛大的母牛聚会,聚会地点在XX 号农场。共有MM 条单行道分别连接两个农场,且通过路ii 需要花 TiT_i 时间。每头母牛都必须参加宴会,并且在宴会结束时回到自己的领地,但是每头母牛都会选择时间最少的方案。来时的路和去时的路可能不一样,因为路是单向的。每个点都有一个奶牛,求所有的母牛中参加聚会来回的最长时间。

输入格式

11行包含33个整数NMN 、MXX 。在第2M+12~M +1行中,第i+1i +1描述道路i ,有33个整数:AiA_iBiB_i TiT_i ,表示从AiA_i 号农场到BiB_i 号农场需要TiT_i 时间。其中,1N10001XN1M1000001Ti1001≤N ≤1000,1≤X≤N ,1≤M ≤100 000,1≤Ti ≤100

输出格式

单行输出母牛必须花费的时间最大值。

样例

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
10

来源

POJ3268 Silver Cow Party

USACO 2007 February Silver