UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3445. [Usaco2014 Feb] Roadblock

统计 下载数据

Description

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

Input

 第一行,两个整数NM. 1 <=N<=250, 1<=M<=250000 

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

Output

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

Sample Input

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.

Sample Output

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

Hint

Source

Gold