JOI logo
日本情報オリンピック 第2回 女性部門

2022年1月24日
情報オリンピック日本委員会

問題
  タクシー 2 (Taxis 2) (配点 100点)
  時間制限 : 4 sec / メモリ制限 : 1024 MB

問題文

IOI 国には,1 から N までの番号が付けられた N 個の町と,1 から M までの番号が付けられた M 本の道がある.

それぞれの道は,タクシーでのみ通行可能である.道 i (1 ≦ i ≦ M) のタクシーは町 Ai と町 Bi双方向に移動でき,そのタクシーの色は,Ci = 1 のとき赤色,Ci = 2 のとき青色である.タクシーには料金がかかり,乗車すると以下のように所持金が変化する.

あなたは IOI 国の町 1 に住んでおり,以下の Q 個の質問の答えを知っておきたい.j 番目 (1 ≦ j ≦ Q) の質問は以下の通りである.

町とタクシーの情報,そして質問の内容が与えられたとき,すべての質問に答えるプログラムを作成せよ.

制約

小課題

  1. (9 点) M = N - 1(Ai, Bi) = (i, i + 1) (1 ≦ i ≦ M),Q = 1N ≦ 100L ≦ 100
  2. (19 点) M = N - 1(Ai, Bi) = (i, i + 1) (1 ≦ i ≦ M),Q = 1
  3. (19 点) M = N - 1(Ai, Bi) = (i, i + 1) (1 ≦ i ≦ M).
  4. (16 点) N ≦ 50 000M ≦ 50 000Q = 1Ci = 1 (1 ≦ i ≦ M).
  5. (20 点) N ≦ 50 000M ≦ 50 000Q = 1
  6. (12 点) N ≦ 50 000M ≦ 50 000Q ≦ 50 000
  7. (5 点) 追加の制約はない.

採点に関する注意

すべての提出はジャッジシステム上で採点される.

提出されたソースコードは,小課題に対応するすべての採点用入力データについて正しい結果を返したとき,その小課題について正解と認められる.

各提出の得点は,提出されたソースコードについて正解と認められた小課題の得点の合計である.

この課題の得点は,この課題に対するすべての提出の得点の最大値である.

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる.

入力

入力は以下の形式で標準入力から与えられる.
N M Q L
A1 B1 C1
A2 B2 C2
:
AM BM CM
T1
T2
:
TQ

出力

標準出力に Q 行で出力せよ.j 行目 (1 ≦ j ≦ Q) には,j 番目の質問の答えを出力せよ.

入出力例

入力例 1
7 6 1 10
1 2 2
2 3 1
3 4 2
4 5 1
5 6 1
6 7 2
5

出力例 1
10

1 → 町 2 → 町 3 → 町 4 → 町 5 の経路で移動するならば,順に青,赤,青,赤のタクシーに乗ることになる.すると,最初に所持金が 10 円あった場合,所持金は 10 円 → 5 円 → 4 円 → 2 円 → 1 円となり,1 円以上を残した状態で町 5 に到着できる.

一方,最初の所持金が 9 円以下の場合,1 円以上を残した状態で町 5 に到着することはできない.

この入力例は小課題 1, 2, 3, 5, 6, 7 の制約を満たす.


入力例 2
10 9 3 25
1 2 2
2 3 1
3 4 1
4 5 1
5 6 2
6 7 1
7 8 1
8 9 1
9 10 2
10
9
3

出力例 2
Large
22
4

例えば,1 番目の質問について考えよう.

1 から出発して町 10 に移動するとき,町 1 → 町 2 → … → 町 9 → 町 10 の経路をたどることになる.しかし,最初に L (= 25) 円持っていたとしても,タクシーを使うごとに所持金が 25 円 → 12 円 → 11 円 → 10 円 → … と減っていき,1 円以上を残して町 10 にたどり着くことはできない.よって,Large と出力しなければならない.

この入力例は小課題 3, 6, 7 の制約を満たす.


入力例 3
5 6 1 1000000000
1 4 1
1 5 1
4 5 1
3 4 1
3 5 1
2 3 1
2

出力例 3
4

1 → 町 5 → 町 3 → 町 2 の経路で移動するならば,赤いタクシーに 3 回乗ることになる.すると,最初に所持金が 4 円あった場合,所持金は 4 円 → 3 円 → 2 円 → 1 円となり,1 円以上を残した状態で町 2 に到着できる.

一方,最初の所持金が 3 円以下の場合,1 円以上を残した状態で町 2 に到着することはできない.

この入力例は小課題 4, 5, 6, 7 の制約を満たす.


入力例 4
9 11 5 10
1 2 1
1 3 2
2 3 2
2 9 2
3 9 1
4 9 1
8 9 1
5 8 1
5 7 1
4 7 2
6 7 2
2
6
7
8
9

出力例 4
2
Large
7
5
3

この入力例は小課題 6, 7 の制約を満たす.