#P1821. [USACO07FEB] Cow Party S
[USACO07FEB] Cow Party S
题目描述
寒假到了, 头牛都要去参加一场在编号为 的牛的农场举行的派对,农场之间有 条有向路,每条路都有一定的长度。
每头牛参加完派对后都必须回家,无论是去参加派对还是回家,每头牛都会选择最短路径,求这 头牛的最短路径(一个来回)中最长的一条路径长度。
输入格式
第一行有三个整数,分别表示牛的数量 ,道路数 和派对农场编号 。
接下来 行,每行三个整数 ,表示存在一条由 通向 的长度为 的道路。
输出格式
输出一行一个整数表示答案。
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 解释
数据规模与约定
对于全部的测试点,保证 ,,,,保证从任何一个结点出发都能到达 号结点,且从 出发可以到达其他所有节点。