Roadblock

Roadblock

题目描述

有一个无向图,共N个节点,编号1至N,共M条边。FJ在节点1,它想到达节点N。FJ总是会选择最短路径到达节点N。作为捣蛋的奶牛Bessie,它想尽量延迟FJ到达节点N的时间,于是Bessie决定从M条边之中选择某一条边,使得改边的长度变成原来的两倍,由于智商的问题,Bessie不知道选择加倍哪条边的长度才能使得FJ到达N号节点的时间最迟。注意:不管Bessie选择加倍哪条边的长度,FJ总是会从1号节点开始走最短路径到达N号点。

输入格式

第一行,两个整数N和M.1<=N<=250,1<=M<=250000。
接下来有M行,每行三个整数:A,B,L,表示节点A和节点B之间有一条长度为L的无向边。1<=L<=1000000。

输出格式

一个整数。Bessie选择了加倍某一条边的长度后,奶牛FJ从节点1到达节点N的最短路径是多少。但是输出的格式有变化,假设Bessie没有加倍某一条边的长度之前,FJ从1号节点到达N号节点的最短路径是X;在Bessie加倍某一条边的长度之后,FJ从1号节点到达N号节点的最短路径是Y,那么你输出的结果是Y-X。

样例输入

5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2
INPUT DETAILS: There are 5 fields and 7 pathways. Currently, the shortest path from the house (field 1) to the barn (field 5) is 1-3-4-5 of total length 1+3+2=6.

样例输出

2
(把节点3到节点4的边从原来的长度3变成长度6)

提示

Gold

信息

难度
9
分类
(无)
标签
递交数
11
已通过
3
通过率
27%
上传者