道路阻塞(Roadblock) - 银组版

时间限制:1S 内存限制:128MB

问题描述

农夫John每个早上起床后都会从他的房子走去他的谷仓。这个农场由N个地区构成(1 <= N <= 250),地区之间由M条双向道路连接(1 <= M <= 25,000),每条道路都有一个确定的长度。农夫John的房子在地区1,而他的谷仓位于地区N。没有两条道路连接同样的两个区域,并且任何两个区域都是可以通过走一些路径相互到达的。当农夫John从一个地区前往另一个的时候,他总是会选择最短路径包含了的那条路。

农夫John的奶牛们还是一如既往的要使坏,她们决定要阻挠农夫John的路线。她们建造一些路障放在其中的一条路上,使得这条路的的长度加倍。奶牛们希望选择一条路来阻塞,使得农夫John从房子到达农场的最短距离最大,请帮助奶牛们计算这样阻塞之后的最短路径最大会增加多少。

输入描述

第一行:以空格分隔的两个整数N和M;

第2到第M+1行:每行分别给出三个整数A_i, B_i, L_i,表示A_i 和B_i 之间存在一条双向的长度为L_i 的道路,A_i 和B_i 都在1..N的范围内,L_i为不大于1,000,000的正整数。

输出描述

输出一个整数,即阻塞一条道路后,农夫John从房子到农场的最短距离,最大的会增加的长度。

样例输入

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

样例输出

2

样例说明

农夫John本来的路线为1-3-4-5,路线总长度为6。

奶牛们阻塞了地区3和地区4之间的道路(将长度3变为长度6),这样农夫John的路线就变成了1-3-5,总长度为8,比未阻塞前增加了2, 所以输出2。

附加说明

原文题面:

Problem 2: Roadblock [Brian Dean]

Every morning, FJ wakes up and walks across the farm from his house to the barn. The farm is a collection of N fields (1 <= N <= 250) connected by M bidirectional pathways (1 <= M <= 25,000), each with an associated length. FJ's house is in field 1, and the barn is in field N. No pair of fields is joined by multiple redundant pathways, and it is possible to travel between any pair of fields in the farm by walking along an appropriate sequence of pathways. When traveling from one field to another, FJ always selects a route consisting of a sequence of pathways having minimum total length.

Farmer John's cows, up to no good as always, have decided to interfere with his morning routine. They plan to build a pile of hay bales on exactly one of the M pathways on the farm, doubling its length. The cows wish to select a pathway to block so that they maximize the increase in FJ's distance from the house to the barn. Please help the cows determine by how much they can lengthen FJ's route.

PROBLEM NAME: rblock

INPUT FORMAT:

  • Line 1: Two space-separated integers, N and M.

  • Lines 2..1+M: Line j+1 describes the jth bidirectional pathway in terms of three space-separated integers: A_j B_j L_j, where A_j and B_j are indices in the range 1..N indicating the fields joined by the pathway, and L_j is the length of the pathway (in the range 1...1,000,000).

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.

OUTPUT FORMAT:

  • Line 1: The maximum possible increase in the total length of FJ's shortest route made possible by doubling the length of a single pathway.

OUTPUT DETAILS:

If the cows double the length of the pathway from field 3 to field 4 (increasing its length from 3 to 6), then FJ's shortest route is now 1-3-5, of total length 1+7=8, larger by two than the previous shortest route length.

题目来源

USACO 2014 February Contest, Silver