TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • 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