3033 : 길 잃은 제리
- 제한시간
- 2000 ms
- 메모리제한
- 512 MB
- 해결횟수
- 33 회
- 시도횟수
- 131 회
문제
톰에게 쫒기고 있던 제리가 어느 대저택에 숨었다.
톰을 겨우 따돌렸다고 생각한 제리는 저택을 나와 집으로 갈 작정이다.
그런데 이 저택을 나가는 길을 알 수가 없었다.
이 저택에는 방이 N개 있으며, 1, 2, ..., N의 번호가 매겨져있다.
또한 복도가 M개 있고, i(1 ≦ i ≦ M)번 복도는 방 Ai와 방 Bi를 연결한다.
제리는 이 복도를 어느 방향으로든 지나갈 수 있으며 복도 i를 지나는 데는 Di 분 걸린다.
복도 이외에 방과 방 사이를 이동하는 다른 방법은 없다.
이 저택에 있는 방들의 실내 온도는 각각 일정하게 조절되고 있는데,
제리에게는 너무 춥거나 적당하거나, 너무 더운 온도이다.
제리는 갑작스러운 온도 변화에 적응하지 못한다.
마지막에 너무 추운 방을 나오고 나서 X 분 미만 동안 너무 더운 방에 들어갈 수 없다.
마찬가지로 마지막에 너무 더운 방을 나오고 나서 X 분 미만 동안 너무 추운 방에 들어갈 수 없다.
제리는 이동 중에 방에 들어서자마자 방에서 나와야한다. 방주인에게 들키면 잡히기 때문이다.
또한 복도 중간에 되돌아가거나 복도 i를 Di보다 오래 걸쳐 통과 할 수 없다.
그러나 한 번 방문한 방에 다시 들어가거나, 한번 사용한 복도를 다시 사용하는 것은 허용된다.
제리는 현재 방 1에 있다. 이 방은 제리에게 너무 춥다.
제리는 저택의 출구가 있는 N번 방에 도착하면 집에서 탈출 할 수 있다.
제리가 저택을 탈출하는 데 걸리는 최소 시간을 구하라.
입력 예 1을 보면 방을 1 → 2 → 3 → 4 → 5 → 6 → 5 → 8로 이동하는 것이 최소 시간이다.
입력 예 2는 일부 객실의 쌍 (예를 들어 방 1과 방 5)을 연결하는 복도가 여러 개 있다는 것에 유의하라.
입력형식
첫 행에 세 정수 N, M, X(2 ≦ N ≦ 10000, 1 ≦ M ≦ 20000, 1 ≦ X ≦ 200) 가 주어진다.
이것은 대저택에 N개의 방과 M개의 복도가 있고 제리가 온도에 적응하는데 X분이 걸린다는 의미이다.
다음 N(1 ≦ i ≦ N)행에 방 i의 온도를 나타내는 정수 Ti (0 ≦ Ti ≦ 2)가 주어진다.
Ti = 0 인 경우 너무 추운 경우를, Ti = 1 인 경우 적당한 온도를, Ti = 2인 경우 더운 경우를 의미한다. T1 = 0 인 것이 보장된다.
다음 M(1 ≦ j ≦ M)개의 행에는 3 개의 정수 Aj, Bj, Dj (1 ≦ Aj < Bj ≦ N, 1 ≦ Dj ≦ 200)가 공백을 구분하여 주어진다.
이것은 복도 j가 방 Aj와 방 Bj를 통과하는데 Dj 분 걸리는 것을 나타낸다.
같은 방 쌍을 연결하는 복도가 여러 개 있을 수 있다는 점에 유의하라.
주어진 입력 데이터에서 제리가 저택을 탈출 할 수 있다는 점이 보장된다.
출력형식
입력 예복사하기 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 |
입력 예복사하기 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 |
