길 잃은 제리 > 문제은행



알고리즘 최단거리

3033 : 길 잃은 제리

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 96 회    시도횟수: 235 회   



톰에게 쫒기고 있던 제리가 어느 대저택에 숨었다.

톰을 겨우 따돌렸다고 생각한 제리는 저택을 나와 집으로 갈 작정이다.

그런데 이 저택을 나가는 길을 알 수가 없었다.

이 저택에는 방이 N개 있으며, 1, 2, ..., N의 번호가 매겨져있다.

또한 복도가 M개 있고, i(1 i M)번 복도는 방 Ai와 방 Bi를 연결한다.

 

제리는 이 복도를 어느 방향으로든 지나갈 수 있으며 복도 i를 지나는 데는 Di 분 걸린다

복도 이외에 방과 방 사이를 이동하는 다른 방법은 없다.

 

이 저택에 있는 방들의 실내 온도는 각각 일정하게 조절되고 있는데

제리에게는 너무 춥거나 적당하거나, 너무 더운 온도이다

제리는 갑작스러운 온도 변화에 적응하지 못한다.

마지막에 너무 추운 방을 나오고 나서 X 분 미만 동안 너무 더운 방에 들어갈 수 없다.

마찬가지로 마지막에 너무 더운 방을 나오고 나서 X 분 미만 동안 너무 추운 방에 들어갈 수 없다

제리는 이동 중에 방에 들어서자마자 방에서 나와야한다. 방주인에게 들키면 잡히기 때문이다.

 

또한 복도 중간에 되돌아가거나 복도 iDi보다 오래 걸쳐 통과 할 수 없다

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

제리는 현재 방 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





dijkstra, heap, priority-queue

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 031-388-0999 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.