题目描述

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

输入格式

第$1$行包含$3$个整数$N 、M$ 和$X$ 。在第$2～M +1$行中，第$i +1$描述道路i ，有$3$个整数：$A_i$ 、$B_i$和$T_i$，表示从$A_i$号农场到$B_i$号农场需要$T_i$ 时间。其中，$1≤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