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




可复制的 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