P2680 [NOIP 2015 Senior] Transportation Plan

NOIP 2015 Day 2 T3.

In the year $2044$, humanity entered the cosmic era. Country L has $n$ planets and $n-1$ bidirectional routes. Each route is built between two planets, and these $n-1$ routes connect all the planets in Country L. Xiao P runs a logistics company that has many transportation plans. Each plan is as follows: a cargo spaceship needs to travel from planet $u_i$ to planet $v_i$ along the fastest space route. Obviously, traversing a route takes time. For route $j$, any spaceship takes time $t_j$ to traverse it, and any two spaceships do not interfere with each other. To encourage technological innovation, the king of Country L allows Xiao P’s logistics company to participate in route construction, that is, to transform one route into a wormhole. Traversing the wormhole takes no time. Before the wormhole is completed, Xiao P’s company has already pre-booked $m$ transportation plans. After the wormhole is completed, these $m$ plans will start simultaneously, and all spaceships depart together. When all $m$ plans are completed, Xiao P’s company finishes this phase of work. If Xiao P can freely choose which route to convert into a wormhole, find the minimum time required for the company to complete this phase of work.

The first line contains two positive integers $n, m$, representing the number of planets in Country L and the number of transportation plans pre-booked by Xiao P’s company. Planets are numbered from $1$ to $n$. The next $n-1$ lines describe the construction of the routes. The $i$-th line contains three integers $a_i, b_i$, and $t_i$, indicating that the $i$-th bidirectional route is built between planets $a_i$ and $b_i$, and any spaceship takes time $t_i$ to traverse it. The next $m$ lines describe the transportation plans. The $j$-th line contains two positive integers $u_j$ and $v_j$, indicating that the $j$-th plan is to travel from planet $u_j$ to planet $v_j$.

Output one integer, the minimum time required for Xiao P’s logistics company to complete this phase of work.

The Constraints and characteristics of all testdata are shown in the table below. | Test point ID | $n = $ | $m = $ | Convention | | :-: | :-: | :-: | :-: | | 1 | $100$ | $1$ | | | 2 | ^ | $100$ | The $i$-th route connects planet $i$ and planet $i + 1$. | | 3 | ^ | ^ | | | 4 | $2000$ | $1$ | ^ | | 5 | $1000$ | $1000$ | The $i$-th route connects planet $i$ and planet $i + 1$. | | 6 | $2000$ | $2000$ | ^ | | 7 | $3000$ | $3000$ | ^ | | 8 | $1000$ | $1000$ | | | 9 | $2000$ | $2000$ | ^ | | 10 | $3000$ | $3000$ | ^ | | 11 | $80000$ | $1$ | ^ | | 12 | $100000$ | ^ | ^ | | 13 | $70000$ | $70000$ | The $i$-th route connects planet $i$ and planet $i + 1$. | | 14 | $80000$ | $80000$ | ^ | | 15 | $90000$ | $90000$ | ^ | | 16 | $100000$ | $100000$ | ^ | | 17 | $80000$ | $80000$ | | | 18 | $90000$ | $90000$ | ^ | | 19 | $100000$ | $100000$ | ^ | | 20 | $300000$ | $300000$ | ^ | | All testdata | | | $1 \le a _ i, b _ i, u _ j, v _ j \le n$，$0 \le t _ i \le 1000$ | Please pay attention to the impact of constant factors on program efficiency. Translated by ChatGPT 5