← 返回题目列表

AtCoder · joisc2022_l

L. 重建项目

中文机器翻译题面 查看原题

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

復興事業 (Reconstruction Project) - 原题 PDF 第 1 页
原题PDF第1页
復興事業 (Reconstruction Project) - 原题 PDF 第 2 页
原题PDF第2页
復興事業 (Reconstruction Project) - 原题 PDF 第 3 页
原题PDF第3页
復興事業 (Reconstruction Project) - 原题 PDF 第 4 页
原题PDF第4页
復興事業 (Reconstruction Project) - 原题 PDF 第 5 页
原题PDF第5页
可复制的 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