← 返回题目列表

AtCoder · joisc2018_l

L. 野猪

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

以下是来自日本的官方新闻原版PDF,已经完整保存和染色。

イノシシ (Wild Boar) - 原题 PDF 第 1 页
原题PDF第1页
イノシシ (Wild Boar) - 原题 PDF 第 2 页
原题PDF第2页
イノシシ (Wild Boar) - 原题 PDF 第 3 页
原题PDF第3页
イノシシ (Wild Boar) - 原题 PDF 第 4 页
原始 PDF 第 4 部分
可复制的 PDF 提取文本
The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                        Contest Day 4 – Wild Boar


                 イノシシ(Wild Boar)



 イノシシのJOI 君が住んでいるIOI 森にはN 個の餌場と,M 本の道がある.i (1 ≦i ≦M) 番目の道は餌
場Ai と餌場Bi を双方向に結んでおり,JOI 君はこの道を移動するのにCi 時間かかる.どの餌場から他の
どの餌場にも,1 本以上の道を辿って到達できる.
  JOI 君は,引き返すことが苦手なので,道の途中で引き返して,もとの餌場に戻ることができない.ま
た,道を通って次の餌場にたどり着いたときにも,今来た道を辿って直前に訪れていた餌場に戻ることが
できない.
  JOI 君は,毎日,補給計画に従って餌を補給する.1日分のJOI 君の補給計画はL 個の餌場の列X1, X2, . . . , XL
からなる.JOI 君は,餌場X1 から補給を開始して,この順に餌場を訪れて,餌場XL で補給を終える.途
中で他の餌場を経由してもよい.同じ餌場で複数回補給することもありうるが,各j (1 ≦j ≦L −1) につ
いて,X j , X j+1 を満たす.補給計画によっては,その計画を実行できないこともありうる.
 最初,JOI 君は,初期の補給計画X1, X2, . . . , XL を決める.JOI 君は,k (1 ≦k ≦T) 日目の朝に,この補
給計画のPk 番目の値をQk に変更して,その日の補給を行う.つまり,XPk の値をQk に変更する.変更
後の補給計画においても,各j (1 ≦j ≦L −1) について,X j , X j+1 を満たす.
  T 日間の補給計画それぞれについて,その補給計画が実行できるかどうかを判定し,もし実行できると
きは,その補給計画に従って餌を補給するのにかかる最小時間を求めよ.


課題

  IOI 森とJOI 君の補給計画についての情報が与えられたとき,T 日間の補給計画それぞれについて,そ
の補給計画が実行できるかどうかを判定し,もし実行できるときは,その補給計画に従って餌を補給する
のにかかる最小時間を求めるプログラムを作成せよ.


入力

 標準入力から以下の入力を読み込め.

   • 1 行目には4 個の整数N, M, T, L が空白を区切りとして書かれている.これらは,IOI 森にはN 個
   の餌場とM 本の道があり,JOI 君がT 日間の補給計画を考え,補給計画の列の長さがL であること
   を表す.

   • 続くM 行のうちのi 行目(1 ≦i ≦M) には,3 個の整数Ai, Bi, Ci が空白を区切りとして書かれてい
   る.これはi 番目の道が,餌場Ai と餌場Bi を双方向に結んでおり,JOI 君はこの道を移動するのに
      Ci 時間かかることを表す.

   • 続くL 行のうちのj 行目(1 ≦j ≦L) には,1 個の整数X j が書かれている.これは初期の補給計画が
    列X1, X2, . . . , XL であることを表す.

   • 続くT 行のうちのk 行目(1 ≦k ≦T) には,2 個の整数Pk, Qk が空白を区切りとして書かれている.
   これはJOI 君が,k 日目の朝に,補給計画のPk 番目の値をQk に変更することを表す.



                      イノシシ– 1 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                        Contest Day 4 – Wild Boar


出力

 標準出力にT 行で出力せよ.k 行目(1 ≦k ≦T) には,k 日目の補給計画について,もし補給計画を実行
できないならば-1 を出力し,実行できるならば実行にかかる最小時間を出力せよ.


制限

 すべての入力データは以下の条件を満たす.

   • 2 ≦N ≦2 000.

   • N −1 ≦M ≦2 000.

   • 1 ≦T ≦100 000.

   • 2 ≦L ≦100 000.

   • 1 ≦Ai < Bi ≦N (1 ≦i ≦M).

   • (Ai, Bi) , (Aj, Bj) (1 ≦i <  j ≦M).

   • どの餌場から他のどの餌場にも,1 本以上の道を辿って到達できる.

   • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦M).

   • 1 ≦Xj ≦N (1 ≦j ≦L).

   • 1 ≦Pk ≦L (1 ≦k ≦T).

   • 1 ≦Qk ≦N (1 ≦k ≦T).

   • 各j (1 ≦j ≦L −1) について,X j , X j+1 を満たす.変更後の補給計画においても,各j (1 ≦j ≦L −1)
   について,X j , X j+1 を満たす.


小課題

 この課題では小課題は全部で4 個ある.各小課題の配点および追加の制限は以下の通りである.

小課題1 [12 点]

   • N ≦10.

   • M ≦10.

   • T = 1.

   • L ≦10.

   • Ci ≦10 (1 ≦i ≦M).


                      イノシシ– 2 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                        Contest Day 4 – Wild Boar


小課題2 [35 点]

   • N ≦500.

   • M ≦500.

   • T = 1.


小課題3 [15 点]

   • T = 1.


小課題4 [38 点]

 追加の制約はない.


入出力例

  入力例1        出力例1
   3 3 1 3              3
   1 2 1
   2 3 1
   1 3 1
   1
   2
   3
   3 1

 入力例1 では,初期の補給計画は1, 2, 3 である.JOI 君は,1 日目の朝に,この補給計画の3 番目の値を
1 に変更する.従って,1 日目の補給計画は1, 2, 1 である.
 まず,JOI 君は,餌場1 で補給する.次に,道1 を用いて餌場1 から餌場2 に移動し,餌場2 で補給す
る.次に,道2 を用いて餌場2 から餌場3 に移動する.最後に,道3 を用いて餌場3 から餌場1 に移動し,
餌場1 で補給する.この補給計画の実行には3 時間かかる.これが最小なので,3 を出力する.
  JOI 君は引き返すことができないので,餌場1 →2 →1 と移動することができないことに注意せよ.





                      イノシシ– 3 / 4

The 17th Japanese Olympiad in Informatics (JOI 2017/2018)
                                                           Spring Training Camp/Qualifying Trial
                                              March 19–25, 2018 (Komaba/Yoyogi, Tokyo)

                                                                        Contest Day 4 – Wild Boar



  入力例2        出力例2
   4 4 4 3              5
   1 2 1                2
   2 3 1                3
   1 3 1                -1
   1 4 1
   4
   1
   3
   3 4
   1 2
   3 2
   2 4

 入力例2 では,1 日目の補給計画は4, 1, 4 である.JOI 君は,最初に餌場4 で補給する.次に,道4
を用いて餌場4 から餌場1 に移動し,餌場1 で補給する.次に,道1, 2, 3, 4 をこの順に用いて,餌場
1 →2 →3 →1 →4 と移動し,餌場4 で補給する.これが最適である.
  4 日目の補給計画は2, 4, 2 である.この補給計画は実行することができないので,-1 を出力する.


  入力例3        出力例3
   5 6 1 5              38
   1 2 8
   1 3 8
   1 4 8
   2 5 2
   3 4 6
   4 5 6
   2
   5
   1
   5
   3
   5 2





                      イノシシ– 4 / 4