TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2765
  • Problem
  • P2765【USACO 2014 February Gold】路障
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    每天早晨,农夫约翰都会散步,起点是他家,终点是谷仓。约翰的农场由M(1 <= M <= 25,000)条双向小路连接的N (1 <= N <= 250)块地构成,编号1到N。每条小路都有一定的长度,约翰的家在1号地,谷仓在第N号地。两块地间最多只有1条道路相连,并且任意两块地都可以相互到达。约翰总是选择最短的线路散步。

    约翰的奶牛都是些捣蛋鬼,它们想作弄一下约翰,决定在M条路中的一条上布置一些障碍,使得该条路的长度翻倍。奶牛们想以此使得约翰从家到谷仓的增加的距离尽可能大,请帮奶牛们算出这个距离。

    (也就是使得约翰从家到谷仓的最小距离尽可能大)

    Input Format

    第一行,两个整数N和M
    接下来M行,每行三个整数A_j B_j L_j,分别代表一条小路的起点、终点和长度(长度范围:1...1,000,000)。

    Output Format

    一个整数,表示所求的距离

    Sample Input 1

    5 7
    2 1 5
    1 3 1
    3 2 8
    3 5 7
    3 4 3
    2 4 7
    4 5 2

    Sample Output 1

    2

    Sample Input 2

    10 9
    4 10 12
    8 4 24
    4 6 10
    4 2 11
    3 6 18
    5 10 11
    5 7 24
    1 7 5
    1 9 17

    Sample Output 2

    24

    Hint

    样例说明:
    奶牛们将3到4的距离翻番,然后约翰散步的路径为1—3—5,总长度为1+7=8,比原来的最短路长度增加了2