2018年3月USACO美國計算機奧賽Open Contest公開賽白金級題3

USACO 2018 US Open Contest, Platinum?Problem 3. Disruption

2018年3月USACO美國計算機奧賽公開賽白金級題3

Farmer John prides himself on running a well-connected farm.

The farm is a collection of?NN?pastures (2≤N≤50,0002≤N≤50,000), pairs of which are connected with?N?1N?1?bi-directional pathways, each having unit length.

Farmer John notices that using an appropriate series of these pathways, it is possible to travel from any pasture to any other pasture.

Although FJ's farm is connected, he worries what might happen if one of the pathways gets blocked, as this would effectively partition his farm into two disjoint sets of pastures, where the cows could travel within each set but not between the sets.

FJ therefore builds a set of?MM?additional bi-directional pathways (1≤M≤50,0001≤M≤50,000), each with a positive integer length at most?109109.

The cows still only use the original pathways for transit, unless one of these becomes blocked.

If one of the original pathways becomes blocked, the farm becomes partitioned into two disjoint pieces, and FJ will select from among his extra pathways a single replacement pathway that re-establishes connectivity between these two pieces, so the cows can once again travel from any pasture to any other pasture.

For each of the original pathways on the farm, help FJ select the shortest suitable replacement pathway.

INPUT FORMAT (file disrupt.in):

The first line of input contains?NN?and?MM.

Each of the next?N?1N?1?lines describes an original pathway using integers?pp,?qq, where?p≠qp≠q?are the pastures connected by the pathway (in the range?1…N1…N).

The remaining?MM?lines each describe an extra pathway in terms of three integers:?pp,?qq, and?rr, where?rr?is the length of the pathway.

At most one pathway runs between any pair of pastures.

OUTPUT FORMAT (file disrupt.out):

For each of the?N?1N?1?original pathways in the order they appear in the input, output the length of the shortest suitable replacement pathway which would re-connect the farm if that original pathway were to be blocked.

If no suitable replacement exists, output -1.

SAMPLE INPUT:

6 3

1 2

1 3

4 1

4 5

6 5

2 3 7

3 6 8

6 4 5

SAMPLE OUTPUT:

7

7

8

5

5

以上就是關于【2018年3月USACO美國計算機奧賽Open Contest公開賽白金級題3】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

2026 NOAI國際AI奧賽中國站即將開考！賽事地址&日程已出！

2027 USAAIO美國AI奧賽啟動報名！MIT/谷歌/Jane Street集體站臺！