Informatica Online Judge

  뱀이 된 경곽이 [1835 / 072B]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 0   Total Tried : 0


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[JOI 16/17 예선]

Background

경곽이는 뜬금없이 뱀이 되었다.

뱀인 경곽이는 어느 큰 저택에서 길을 헤매고 있다.

저택의 주인에게 들키기 전에 저택을 탈출해야만 한다.

이 저택에는 $n$개의 방이 있고 $1$, $2$, $...$, $n$의 번호가 부여되어 있다.

또 복도는 $m$개가 있고 $i$번째 복도는 방 $a_i$과 $b_i$를 연결하고 있다.

경곽이는 모든 복도를 통과할 수 있고 복도 $i$를 통과하는데 $d_i$분이 걸린다.

방과 방 사이의 복도를 통과하는 것 이외에 다른 방법으로는 이동할 수 없다.

이 저택의 방의 온도는 각각 일정하게 조절되고 있다. 각 방의 온도는 경곽이에게 있어서 3가지 종류가 있다. 각 온도는 적당하거나, 너무 높거나, 너무 낮은 것 중 한 가지이다.

경곽이는 변온동물이라 급격한 온도변화는 견딜 수 없으므로 이동할 수 없다.

따라서 만약 너무 온도가 높은 방에 있다가 온도가 너무 낮은 방으로 이동하기 위해서는 최소 $x$분 이상은 흘러야 한다.

물론 너무 온도가 낮은 방에 있다가 너무 온도가 높은 방으로 이동할 때에도 최소 $x$분 이상은 지나야 한다.

경곽이는 이동중에 방에 들어갔다면 바로 방으로부터 나와야 한다. 또 복도 이동 중 중간에 되돌아오거나 복도 $i$를 지나는데 $D_i$이상의 시간을 쓸 수는 없다.

그러나 한 번 방문한 방에 다시 들어가거나 한 번 사용한 복도를 다시 사용하는 것은 허용된다.

경곽이는 현재 1번 방에 있다. 이 방은 경곽이에게는 온도가 너무 낮다.

경곽이는 저택의 출구가 있는 $n$번 방에 들어가면 탈출할 수 있다.

경곽이가 저택을 탈출하는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 3개의 정수 $n$, $m$, $x$가 공백으로 구분되어 입력된다.

두 번째 줄부터 $n$줄에 걸쳐서 $i$번 째방의 온도 $T_i$가 입력된다. 온도는 0이면 너무 온도가 낮은 방, 1이면 적단한 방, 2이면 온도가 너무 높은 방을 의미한다.

다음 줄부터 $m$줄에 걸쳐서 3개의 정수 $a_i$, $b_i$, $D_i$의 값이 공백으로 구분되어 입력된다.

이 값들은 방 $a$와 방 $b$를 연결하는 복도를 통과하는데 걸리는 시간이 $D_i$분 걸린다는 것을 의미한다.

[입력값의 정의역]

$2 ≦ n ≦ 10000, 1 ≦ m ≦ 20000, 1 ≦ x ≦ 200$
$1 ≦ a_i < b_i ≦ n, 1 ≦ D_i ≦ 200$
$0 ≦ Ti ≦ 2$

Output

경곽이가 저택을 탈출하는데 걸리는데 걸리는 최소시간을 출력한다.

IO Example

입력
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

입력2
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

출력2
6

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]