TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1976
  • Problem
  • P1976奶牛开会
    Limits : Time Limit : - MS   Memory Limit : 65536 KB
    Judgment Tips : 1s
    Description

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

    Input Format

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

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

    Output Format

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

    Sample Input 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

    Sample Output 1

    10

    Sample Input 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

    Sample Output 2

    213

    Hint

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

    样例1说明:

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

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


    Source  USACO 2007 February Silver