以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。





可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project
復興事業(Reconstruction Project)
JOI 町はかつて栄えた工業地域であり,物資の運搬のために数多くの駅や線路が建設された.現在は衰退
してしまったが,使われなくなった駅や線路は今もなお残されたままである.
JOI 町にはN 個の駅が残されており,1 からN までの番号が付けられている.またM 本の線路が残され
ており,i 本目(1 ≦i ≦M) の線路は駅Ai と駅Bi を双方向に結び,そのレール幅はWi である.どの駅から
どの駅へもいくつかの線路を通って到達できる.
JOI 町の町長であるあなたは,この残された駅と線路を用いて鉄道会社を誘致し,JOI 町を鉄道の町とし
て復興させることにした.するとこの復興事業にQ 社の鉄道会社が名乗りを挙げた.しかし鉄道会社ごと
に,保有する列車に対応するレール幅が決まっているため,線路のレール幅を列車に合わせるための工事が
必要であることが分かった.
j 番目(1 ≦j ≦Q) の鉄道会社の列車に対応するレール幅はXj である.j 番目の鉄道会社を誘致するには
次の条件を満たす必要がある.
条件どの駅からどの駅へも,レール幅がXj である線路のみを通って到達できる.
この条件を満たすようにするために,あなたは次の工事を好きなだけ行える.
工事線路を1 つ選び,その線路のレール幅を1 だけ増やすまたは減らす.これにはコストが1 だけ
かかる.ただし,レール幅が1 である線路のレール幅をさらに減らすことはできない.
あなたは誘致する鉄道会社を決めるために,各鉄道会社を誘致するのにそれぞれ最小でいくらコストがか
かるのかを見積もりたい.
駅と線路,鉄道会社の情報が与えられたとき,各鉄道会社を誘致するためにかかるコストの最小値を求め
るプログラムを作成せよ.
復興事業– 1 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N M
A1 B1 W1
A2 B2 W2
...
AM BM WM
Q
X1
X2
...
XQ
出力
標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) にはj 番目の鉄道会社を誘致するためにかかるコストの
最小値を出力せよ.
制約
• 2 ≦N ≦500.
• N −1 ≦M ≦100 000.
• 1 ≦Q ≦1 000 000.
• 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
• 1 ≦Wi ≦1 000 000 000 (= 109) (1 ≦i ≦M).
• (Ai, Bi, Wi) , (Aj, Bj, W j) (1 ≦i < j ≦M)
• どの駅からどの駅へもいくつかの線路を通って到達できる.
• 1 ≦Xj ≦1 000 000 000 (= 109) (1 ≦j ≦Q).
• Xj < Xj+1 (1 ≦j ≦Q −1).
復興事業– 2 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project
小課題
1. (3 点) M ≦16,Q ≦10.
2. (4 点) Q ≦10.
3. (7 点) Bi = Ai + 1 (1 ≦i ≦M).
4. (28 点) M ≦1 000.
5. (35 点) Q ≦20 000.
6. (23 点) 追加の制約はない.
入出力例
入力例1 出力例1
5 10 8
1 2 8 2
1 3 13 5
1 4 5 10
1 5 11 9
1 5 3 21
2 3 7
2 4 15
3 4 6
3 5 6
4 5 2
6
3
6
8
10
13
17
例えば1 番目の鉄道会社を誘致するとき,以下のように工事を行うとコストが8 かかる.
1. 6 本目の線路のレール幅を4 だけ減らす.これにはコストが4 だけかかる.
復興事業– 3 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project
2. 9 本目の線路のレール幅を3 だけ減らす.これにはコストが3 だけかかる.
3. 10 本目の線路のレール幅を1 だけ増やす.これにはコストが1 だけかかる.
コスト8 未満で1 番目の鉄道会社を誘致することはできないので,1 行目には8 を出力する.
この入力例は小課題1, 2, 4, 5, 6 の制約を満たす.
入力例2 出力例2
3 4 1
1 2 1 1
1 2 4 2
2 3 2 0
2 3 4
4
1
2
3
4
この入力例はすべての小課題の制約を満たす.
復興事業– 4 / 5
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 4 – Reconstruction Project
入力例3 出力例3
10 20 1121073688
6 7 914727791 761832468
1 8 771674531 1026806785
3 5 632918108 1316097872
5 9 329296846 1321500065
1 7 237501112 1445238392
4 9 303328173 1637513141
2 6 216298255 1621778548
2 10 504024991 1733953031
3 8 158236886 1738749711
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
この入力例は小課題2, 4, 5, 6 の制約を満たす.
復興事業– 5 / 5