A29213.[USACO07FEB] Cow Party S

普及/提高-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

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

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

Data Credits: Macw07

输入格式

第一行有三个整数,分别表示牛的数量 nn,道路数 mm 和派对农场编号 xx

接下来 mm 行,每行三个整数 u,v,wu, v, w,表示存在一条由 uu 通向 vv 的长度为 ww 的道路。

输出格式

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

输入输出样例

  • 输入#1

    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

    输出#1

    10

说明/提示

数据规模与约定

对于全部的测试点,保证 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 出发可以到达其他所有节点。

首页