TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P1976
  • 問題
  • P1976奶牛开会
    制限 : 時間制限 : - MS   メモリ制限 : 65536 KB
    審判説明 : 1s
    問題説明

       约翰的农场有N个牛棚,牛棚编号1到N。每个牛棚都有1只奶牛要参加在X号牛棚举行的奶牛大会。共有M条单向路连接着牛棚,第i条路需要Ti的时间来通过。两个牛棚间可能有多条道路相连。
       奶牛们都很懒,所以不管是前去X牛棚开会还是返回自己居住的牛棚,她们都采用了用时最少的路线.那么,用时最多的奶牛需要多少时间来回呢?请你帮忙计算!
       数据保证每只奶牛都能成功往返。

    入力形式

    第一行三个正整数n, m, x(n是节点个数,m是有向边的条数,x是参加聚会的地点编号)

    接下来m行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.

    出力形式

    一行:一个整数,表示所有开会的奶牛中,往返需要花费总时间的最大值.

    サンプル入力 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

    サンプル入力 2

    6 20 3
    3 2 45
    6 1 66
    6 2 31
    2 4 94
    5 3 46
    5 2 79
    3 1 64
    4 3 74
    3 5 59
    1 6 93
    3 6 45
    6 4 40
    3 4 67
    1 3 61
    1 2 42
    4 2 50
    4 1 55
    2 6 93
    5 4 95
    1 4 54

    サンプル出力 2

    213

    ヒント

     1 ≤ n ≤ 1000  , 1 ≤ m ≤ 6000,   0<=Ti<=100
     

    样例1说明:

    共有4只奶牛参加聚会,有8条路,聚会位于第2个农场.

    第4只奶牛可以直接到聚会所在地(花费3时间),然后返程路线经过第1和第3个农场(花费7时间),总共10时间.


    ソース  USACO 2007 February Silver