ヘビの JOI 君 (Snake JOI)
日本語
Language
Contribute a translation- Time limit
- 10000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
ヘビの JOI 君は，ある大きな屋敷に迷い込んでしまった．屋敷の住人に見つかる前に，屋敷を脱出しなければならない．
この屋敷には部屋が \(N\) 個あり，\(1, 2, \ldots, N\) の番号が付けられている．また，廊下が \(M\) 本あり，\(i\) 本目の廊下 (\(1 \leqq i \leqq M\)) は部屋 \(A_i\) と部屋 \(B_i\) を結んでいる．JOI 君はこれらの廊下をどちらの向きにも通ることができ，廊下 \(i\) を通るのには \(D_i\) 分かかる．部屋と部屋の間を廊下を通る以外の手段で移動する方法はない．
この屋敷の部屋の温度はそれぞれ一定に調節されており，JOI 君にとって寒すぎるか，快適であるか，暑すぎるかである．JOI 君は，急な温度変化に対応できないため，最後に寒すぎる部屋を出てから \(X\) 分未満のうちに暑すぎる部屋に入ることはできない．同様に，最後に暑すぎる部屋を出てから \(X\) 分未満のうちに寒すぎる部屋に入ることもできない．
JOI 君は，移動中に部屋に入るとすぐに部屋から出なければならない．また，廊下の途中で引き返したり，廊下 \(i\) を \(D_i\) 分より長い時間かけて通ることもできない．ただし，一度訪れた部屋にもう一度入ることや，一度使った廊下をもう一度使うことは許される．
JOI 君は現在部屋 \(1\) にいる．この部屋は JOI 君にとって寒すぎる．JOI 君は屋敷の出口のある部屋 \(N\) に入ると，屋敷から脱出できる．
JOI 君が屋敷から脱出するのにかかる最短の時間を求めよ．
Input
入力は \(1 + N + M\) 行からなる．
\(1\) 行目には，\(3\) 個の整数 \(N, M, X\) (\(2 \leqq N \leqq 10\,000\)，\(1 \leqq M \leqq 20\,000\)，\(1 \leqq X \leqq 200\)) が空白を区切りとして書かれている．これは，屋敷に \(N\) 個の部屋と \(M\) 本の廊下があり，JOI 君が温度変化に対応するのに \(X\) 分かかることを表す．
続く \(N\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N\)) には，部屋 \(i\) の温度を表す整数 \(T_i\) (\(0 \leqq T_i \leqq 2\)) が書かれている．JOI 君にとって部屋 \(i\) は，\(T_i = 0\) のとき寒すぎ，\(T_i = 1\) のとき快適であり，\(T_i = 2\) のとき暑すぎる．\(T_1 = 0\) であることが保証されている．
続く \(M\) 行のうちの \(j\) 行目 (\(1 \leqq j \leqq M\)) には，\(3\) 個の整数 \(A_j, B_j, D_j\) (\(1 \leqq A_j < B_j \leqq N\)，\(1 \leqq D_j \leqq 200\)) が空白を区切りとして書かれている．これは，廊下 \(j\) が部屋 \(A_j\) と部屋 \(B_j\) を結んでおり，通るのに \(D_j\) 分かかることを表す．同じ部屋の組を結ぶ廊下が複数ある可能性があることに注意せよ．
与えられる入力データでは，JOI 君が屋敷から脱出できることは保証されている．
Output
JOI 君が屋敷から脱出するのに最短で何分かかるかを表す整数を \(1\) 行で出力せよ．
Examples
8 10 4 0 1 1 2 1 1 2 0 1 2 1 1 3 1 2 3 3 2 4 5 3 4 1 4 5 1 5 6 1 5 8 1 1 7 2 7 8 2
9
入力例 \(1\) では，部屋を \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 5 \rightarrow 8\) の順に移動するのが最短となる．
15 25 4 0 1 1 0 2 1 0 1 1 2 0 0 1 0 1 8 11 1 7 10 1 12 14 1 3 8 1 1 5 1 3 9 1 3 8 1 1 5 1 6 15 1 11 12 1 2 14 1 7 10 1 11 12 1 5 13 1 2 8 1 1 4 1 2 11 1 5 6 1 1 13 1 6 12 1 5 10 1 9 13 1 4 10 1 3 12 1 7 13 1
6
入力例 \(2\) では，いくつかの部屋の組 (たとえば部屋 \(1\) と部屋 \(5\)) を結ぶ廊下が複数ある．
Notes
JOI 2017 · JCIOI · CC BY-SA 4.0
Tags
No tags yet