IOI 2011 day2 1- 악어의 지하 도시(crocodile) > 문제은행 : 정보올림피아드&알고리즘




2677 : 악어의 지하 도시(crocodile)

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
11 회   
시도횟수
31 회   

문제

고고학자 철수는 악어의 신비한 지하 도시를 탐험하다가 위험을 느끼고 도망치게 되었다.

지하 도시는 N개의 방으로 구성되어 있다.

방들을 연결하는 M개의 복도가 있는데, 각 복도는 서로 다른 두 방을 연결하며, 같은 쌍의 방을 연결하는 복도는 최대 1개이다.

복도를 통과하는데 걸리는 시간은 복도마다 다를 수 있다

N개의 방들 중 K개는 바로 탈출이 가능한 “탈출방”이다.

철수는 최초에 방 0에 있다. 철수는 최대한 빨리 탈출방으로 가려고 한다.

 


악어 문지기는 철수가 탈출하는 것을 막으려고 한다.

문지기는 복도 중 임의의 하나를 막을 수 있는 방법이 있다. 어떤 시점이든 단 하나만 막을 수 있다.

즉, 문지기가 새로운 복도를 막으면 이전에 막았던 복도는 열린다.

 


철수의 상황을 좀더 자세히 설명하면 다음과 같다:

철수가 어떤 방을 떠나려고 할 때 문지기는 그 방과 연결된 복도들 중 하나를 막을 수 있다.

철수는 막히지 않은 복도 중 하나를 골라서 다른 방으로 이동한다.

철수가 복도에 일단 들어가고 나면 철수가 이동을 완료할 때 까지는 문지기가 이 복도를 막을 수 없다.

철수가 다른 방에 들어가고 나면 문지기는 (방금 지나온 복도도 당연히 포함하여) 또 다른 복도를 막을 수 있고, 이런 식으로 반복된다.

 


철수는 탈출 계획을 미리 정해 놓기를 원한다.

정확히 말하자면, 각 방 마다, 그 방에 도착하면 어떤 식으로 행동해야 하는 지의 계획이 미리 정해져 있어야 한다.

A가 어떤 방이라고 하자. 만약 A가 탈출방이라면 바로 탈출하면 되므로 별다른 계획이 필요하지 않다.

A가 탈출방이 아니라면 A에 대해서는 다음 중 한가지 형태의 계획이 있어야 한다. 



● 만약 A에 있다면 방 B로 이동하는 것이 우선이다. 만약 그 쪽 복도가 막혀 있으면 방 C로 이동하라.

● 이 계획 하에서는 A에 절대 도달할 수 없으므로, 아무 계획이 없음.

 


어떤 경우에는 (예를 들어 어떤 계획하에서 철수가 싸이클을 도는 경우 등) 문지기가 탈출이 영원히 불가능하도록 만들 수도 있다는 점에 주의하라.

어떤 탈출 계획이 문지기가 어떤 작전을 쓰던지 철수가 유한한 시간 안에 탈출하는 것이 가능하다는 것을 보장하면 

그 계획은 "좋은" 계획이라고 부른다.

어떤 좋은 계획 하에서, 철수가 그 시간이 지난 후에는 반드시 탈출한다고 보장할 수 있는 최소의 시간을 T라고 하자.

그 경우, 그 좋은 계획의 “탈출 시간”은 T라고 말한다.


당신은 좋은 계획이 존재하는 탈출 시간의 최소값 T를 구해야 한다.

 

[예제분석]

방들은 원으로 표시되었고 복도는 줄로 표시되어 있다. 

탈출방들은 굵은 원으로 표시되어 있다. 

초기에 철수는 (삼각형으로 표시된) 방 0 에 있다.
최적의 탈출 계획 중 하나는 다음과 같다. 

  ●​ 방 0 에 있다면, 방 1 로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 2 로이동하라. 

  ●​ 방 2 에 있다면, 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방 4 로
이동하라. 

최악의 경우에 시간 7 을 쓰고 탈출방에 도달할 수 있다. 따라서, travel_plan 은 7 을 리턴해야 한다.
 

 

 

가능한 최적의 계획들 중 하나는 다음과 같다. 

  ●​ ​방 0 에 있으면 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방
2 로 이동하라 

  ●​ ​방 2 에 있으면 방 3 으로 이동하는 것이 우선이다. 만약 그 방향이 막혀 있으면 방
1 로 이동하라 

  ●​ ​방 4 에는 가는 경우가 없으므로 아무 계획이 없다. 

이 계획을 이용하면 철수는 시간 14 를 쓴 이후에는 반드시 탈출할 수 있다.

따라서
travel_plan 은 14 를 리턴해야 한다
 

 

 


입력형식

입력의 첫줄에 N, M, K이 들어오고 그 다음 줄부터 M개의 줄에 R, L이, 그 다음 줄에 K개의 P가 들어온다.

● N - 방의 수. 방은 0 부터 N-1 까지 번호가 붙어 있다. (3 ≤ N ≤ 100,000) 

● M - 복도의 수. 복도는 0 부터 M-1 까지 번호가 붙어 있다. (2 ≤ M ≤ 1,000,000) 

● R - 복도들을 표현하는 정수의 2 차원 배열. 각 i(0≤i<M)에 대해서 복도 i 는 방 R[i][0]와 방 R[i][1]를 연결한다.
       동일한 쌍의 방들을 연결하는 복도는 최대 하나이다. 

● L - 복도를 통과하는데 걸리는 시간을 저장할 일차원 배열. 각 i(0≤i<M)에 대해서
        L[i](1≤L[i]≤1,000,000,000)의 값은 철수가 복도 i 를 통과하는 데 걸리는 시간이다. 

● K - 탈출방의 수. (1≤K<N) 

● P - 탈출방의 번호들을 가지는 크기 K 인 정수의 일차원 배열. 각 i(0≤i<K)에 대해서 P[i]는 i 번째 탈출방의 번호이다.
        방 0 는 탈출방에 포함되지 않는다. (P 에 있는 값들은 모두 다르다.) 

 

탈출방이 아닌 방은 최소한 2 개의 복도가 연결되어 있다고 가정해도 좋다. 

또한, 모든 경우에 T ≤ 1,000,000,000 이하인 좋은 계획이 존재한다고 가정해도 좋다.


출력형식

출력의 첫 줄에 좋은 계획이 존재하는 탈출 시간의 최소값 T를 출력한다.


입력 예

5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4

출력 예

7

입력 예

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3

출력 예

14


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP