BZPRO

#1631. [Usaco2007 Feb]Cow Party

内存限制：64 MiB 时间限制：5 Sec
提交 提交记录 讨论

题目描述

    农场有N(1≤N≤1000)个牛棚，每个牛棚都有1只奶牛要参加在X牛棚举行的奶牛派对．共有M(1≤M≤100000)条单向路连接着牛棚，第i条踣需要Ti的时间来通过．牛们都很懒，所以不管是前去X牛棚参加派对还是返回住所，她们都采用了用时最少的路线．那么，用时最多的奶牛需要多少时间来回呢？

输入格式

第1行:三个用空格隔开的整数.

 第2行到第M+1行,每行三个用空格隔开的整数:Ai, Bi,以及Ti.表示一条道路的起点,终点和需要花费的时间.

输出格式

唯一一行:一个整数: 所有参加聚会的奶牛中,需要花费总时间的最大值.

样例

样例输入


			
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

数据范围与提示

样例说明:


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


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

BZPRO Powered by Remmina.
Github Repository