/
実行時間制限: 5 sec / メモリ制限: 1024 MiB
Score: 100 points
Problem Statement
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 \le i \le 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 \le j \le Q) is X_{j}. 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.
Input
Read the following data from the standard input. Given values are all integers.
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}
Output
Write Q lines to the standard output. The j-th line (1 \le j \le Q) of output should contain the minimum cost to attract the railroad company j.
Constraints
- 2 \le N \le 500.
- N - 1 \le M \le 100\,000.
- 1 \le Q \le 1\,000\,000.
- 1 \le A_{i} < B_{i} \le N (1 \le i \le M).
- 1 \le W_{i} \le 1\,000\,000\,000 (= 10^{9}) (1 \le i \le M).
- (A_{i}, B_{i}, W_{i}) \ne (A_{j}, B_{j}, W_{j}) (1 \le i < j \le M).
- It is possible to travel from any station to any other station using railway tracks.
- 1 \le X_{j} \le 1\,000\,000\,000 (= 10^{9}) (1 \le j \le Q).
- X_{j} < X_{j+1} (1 \le j \le Q - 1).
Subtasks
- (9 points) M \le 16, Q \le 10.
- (11 points) Q \le 10.
- (18 points) B_{i} = A_{i} + 1 (1 \le i \le M).
- (23 points) M \le 1\,000.
- (28 points) Q \le 20\,000.
- (11 points) No additional constraints.
Sample Input 1
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
Sample Output 1
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.
- Decrease the width of the 6-th railway track by 4. The cost is 4.
- Decrease the width of the 9-th railway track by 3. The cost is 3.
- Increase the width of the 10-th railway track by 1. The cost is 1.
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.
Sample Input 2
3 4 1 2 1 1 2 4 2 3 2 2 3 4 4 1 2 3 4
Sample Output 2
1 1 2 0
This sample input satisfies the constraints of all the subtasks.
Sample Input 3
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
Sample Output 3
1121073688 761832468 1026806785 1316097872 1321500065 1445238392 1637513141 1621778548 1733953031 1738749711
This sample input satisfies the constraints of Subtasks 2, 4, 5, 6.
配点 : 100 点
問題文
JOI 町はかつて栄えた工業地域であり,物資の運搬のために数多くの駅や線路が建設された.現在は衰退してしまったが,使われなくなった駅や線路は今もなお残されたままである.
JOI 町には N 個の駅が残されており,1 から N までの番号が付けられている.また M 本の線路が残されており,i 本目 (1 \leqq i \leqq M) の線路は駅 A_{i} と駅 B_{i} を双方向に結び,そのレール幅は W_{i} である.どの駅からどの駅へもいくつかの線路を通って到達できる.
JOI 町の町長であるあなたは,この残された駅と線路を用いて鉄道会社を誘致し,JOI 町を鉄道の町として復興させることにした.するとこの復興事業に Q 社の鉄道会社が名乗りを挙げた.しかし鉄道会社ごとに,保有する列車に対応するレール幅が決まっているため,線路のレール幅を列車に合わせるための工事が必要であることが分かった.
j 番目 (1 \leqq j \leqq Q) の鉄道会社の列車に対応するレール幅は X_{j} である.j 番目の鉄道会社を誘致するには次の条件を満たす必要がある.
- 条件 どの駅からどの駅へも,レール幅が X_{j} である線路のみを通って到達できる.
この条件を満たすようにするために,あなたは次の工事を好きなだけ行える.
- 工事 線路を 1 つ選び,その線路のレール幅を 1 だけ増やすまたは減らす.これにはコストが 1 だけかかる.ただし,レール幅が 1 である線路のレール幅をさらに減らすことはできない.
あなたは誘致する鉄道会社を決めるために,各鉄道会社を誘致するのにそれぞれ最小でいくらコストがかかるのかを見積もりたい.
駅と線路,鉄道会社の情報が与えられたとき,各鉄道会社を誘致するためにかかるコストの最小値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
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}
出力
標準出力に Q 行で出力せよ.j 行目 (1 \leqq j \leqq Q) には j 番目の鉄道会社を誘致するためにかかるコストの最小値を出力せよ.
制約
- 2 \leqq N \leqq 500.
- N - 1 \leqq M \leqq 100\,000.
- 1 \leqq Q \leqq 1\,000\,000.
- 1 \leqq A_{i} < B_{i} \leqq N (1 \leqq i \leqq M).
- 1 \leqq W_{i} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq i \leqq M).
- (A_{i}, B_{i}, W_{i}) \ne (A_{j}, B_{j}, W_{j}) (1 \leqq i < j \leqq M)
- どの駅からどの駅へもいくつかの線路を通って到達できる.
- 1 \leqq X_{j} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq j \leqq Q).
- X_{j} < X_{j+1} (1 \leqq j \leqq Q - 1).
小課題
- (9 点) M \leqq 16,Q \leqq 10.
- (11 点) Q \leqq 10.
- (18 点) B_{i} = A_{i} + 1 (1 \leqq i \leqq M).
- (23 点) M \leqq 1\,000.
- (28 点) Q \leqq 20\,000.
- (11 点) 追加の制約はない.
入力例 1
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
出力例 1
8 2 5 10 9 21
例えば 1 番目の鉄道会社を誘致するとき,以下のように工事を行うとコストが 8 かかる.
- 6 本目の線路のレール幅を 4 だけ減らす.これにはコストが 4 だけかかる.
- 9 本目の線路のレール幅を 3 だけ減らす.これにはコストが 3 だけかかる.
- 10 本目の線路のレール幅を 1 だけ増やす.これにはコストが 1 だけかかる.
コスト 8 未満で 1 番目の鉄道会社を誘致することはできないので,1 行目には 8 を出力する.
この入力例は小課題 1, 2, 4, 5, 6 の制約を満たす.
入力例 2
3 4 1 2 1 1 2 4 2 3 2 2 3 4 4 1 2 3 4
出力例 2
1 1 2 0
この入力例はすべての小課題の制約を満たす.
入力例 3
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
出力例 3
1121073688 761832468 1026806785 1316097872 1321500065 1445238392 1637513141 1621778548 1733953031 1738749711
この入力例は小課題 2, 4, 5, 6 の制約を満たす.