#P1821. [USACO07FEB] Cow Party S

[USACO07FEB] Cow Party S

题目描述

寒假到了,nn 头牛都要去参加一场在编号为 xx 的牛的农场举行的派对,农场之间有 mm 条有向路,每条路都有一定的长度。

每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这 nn 头牛的最短路径(一个来回)中最长的一条路径长度。

输入格式

第一行有三个整数,分别表示牛的数量 nn,道路数 mm 和派对农场编号 xx
接下来 mm 行,每行三个整数 u,v,wu, v, w,表示存在一条由 uu 通向 vv 的长度为 ww 的道路。

输出格式

输出一行一个整数表示答案。

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

提示

样例 1 解释

数据规模与约定

对于全部的测试点,保证 1xn1031 \leq x \leq n \leq 10^31m1051 \leq m \leq 10^51u,vn1 \leq u,v \leq n1w1021 \leq w \leq 10^2,保证从任何一个结点出发都能到达 xx 号结点,且从 xx 出发可以到达其他所有节点。