| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 74 | 37 | 32 | 60.377% |
JOI Town is an industrial area which had flourished some time ago. In order to transport products, many stations and railway tracks were constructed. Though it declined, there remain the stations and the railway tracks which are not used any more
There are $N$ stations in JOI Town, numbered from 1ドル$ to $N$. There remain $M$ railway tracks. The $i$-th railway track (1ドル ≤ i ≤ M$) connects the station $A_i$ and the station $B_i$ bidirectionally. The width of the $i$-th railway track is $W_i$. It is possible to travel from any station to any other station using railway tracks.
You are the mayor of JOI Town. You are planning to attract a railroad company using the remaining stations and railway tracks, and revive the JOI Town as the town of railway. Then, $Q$ railroad companies applied for this revival project. However, the width of the railway track for trains varies for different companies. It turns out that they need to reconstruct the railway tracks so that the width of the railway tracks of JOI Town matches the width of the railway tracks for the trains of a company.
The width of the railway tracks for the trains of the railroad company $j$ (1 ≤ j ≤ Q) is Xj . To attract the railroad company $j,ドル it is required that the following condition is satisfied.
Condition It is possible to travel from any station to any other station using railway tracks of width $X_j$ only.
In order to satisfy the above condition, you can reconstruct the railway tracks as many times as needed.
Reconstruction You choose a railway track. Then you reconstruct the chosen track so that its width will be increased or decreased by 1ドル$. The cost is 1ドル$. However, if the width of a railway track is 1ドル,ドル it is impossible to decrease the width further.
In order to decide on the company to be attracted, you want to estimate the minimum cost to attract each railroad company.
White a program which, given information on the stations, the railway tracks, and the railroad companies, calculates the minimum cost to attract each railroad company.
Read the following data from the standard input. Given values are all integers.
$\begin{align*}& N ,円 M \\ & A_1 ,円 B_1 ,円 W_1 \\ & A_2 ,円 B_2 ,円 W_2 \\ & \vdots \\ & A_M ,円 B_M ,円 W_M \\ & Q \\ & X_1 \\ & X_2 \\ & \vdots \\ & X_Q \end{align*}$
Write $Q$ lines to the standard output. The $j$-th line (1ドル ≤ j ≤ Q$) of output should contain the minimum cost to attract the railroad company $j$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 3 | $M ≤ 16,ドル $Q ≤ 10$. |
| 2 | 4 | $Q ≤ 10$. |
| 3 | 7 | $B_i = A_i + 1$ (1ドル ≤ i ≤ M$). |
| 4 | 28 | $M ≤ 1,000円$. |
| 5 | 35 | $Q ≤ 20,000円$. |
| 6 | 23 | No additional constraints. |
5 10 1 2 8 1 3 13 1 4 5 1 5 11 1 5 3 2 3 7 2 4 15 3 4 6 3 5 6 4 5 2 6 3 6 8 10 13 17
8 2 5 10 9 21
For example, to attract the railroad company 1ドル,ドル it will cost 8ドル$ if you reconstruct the railway tracks as follows.
It is impossible to attract the railroad company 1ドル$ at cost less than 8ドル$. Therefore, output 8ドル$ in the first line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6.
3 4 1 2 1 1 2 4 2 3 2 2 3 4 4 1 2 3 4
1 1 2 0
This sample input satisfies the constraints of all the subtasks.
10 20 6 7 914727791 1 8 771674531 3 5 632918108 5 9 329296846 1 7 237501112 4 9 303328173 2 6 216298255 2 10 504024991 3 8 158236886 1 10 10176179 8 9 918271145 3 6 217165898 3 6 624543444 4 9 70147274 8 9 976983490 6 9 210108505 2 9 972711062 1 10 564567289 3 7 411395464 4 7 952470985 10 115721165 198969744 356664401 429802521 513343279 610443927 741016686 786597783 898772266 903568946
1121073688 761832468 1026806785 1316097872 1321500065 1445238392 1637513141 1621778548 1733953031 1738749711
This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.
Camp > JOI Spring Training Camp > JOI 2021/2022 Spring Training Camp 4-3번
Camp > JOIG Spring Training Camp > JOIG 2021/2022 Spring Training Camp 2-4번