Informatica Online Judge

  방 탈출 [2286 / 08EE]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 8   Total Tried : 8


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

[35th 유문현]

Background

분명히 GSHS 기숙사에서 마이티를 친 후 잤지만 눈을 떠보니 각기 다른 이상한 방 안에 서로 떨어져 갇혀 있는 킹민성과 친구들. 방 안에 있는 건 잡다한 물건들 뿐이었다... 각 방마다 있는 무전기로 서로의 생사를 확인할 수 있었지만, 아무도 이곳에 오게 된 이유를 몰랐다.

우연히 방에서 지도를 찾게 된 킹민성. 지도를 보니 킹민성과 친구들은 하나의 거대한 트리 속에 갇혀 있게 된 것이었다! 트리는 1번 방부터 N번 방까지 있고, 1번부터 N-1번 통로가 방과 방을 잇고 있었다. 통로를 지나가는 데에는 1분이 걸린다. 당연히, 각 방과 통로는 동시에 여러 사람이 있을 만큼의 충분한 크기를 갖고 있다. 또한, 트리에는 Q개의 탈출할 수 있는 방이 있어서, 하나의 방당 오직 한 명의 사람만 탈출할 수 있었다.

지도를 더 자세히 읽어보니, 각 통로마다 Ti가 있어, 앞으로 Ti분 이후에는 통로가 폐쇄된다고 한다. 폐쇄된 통로를 지나가거나, 지나가던 중에 폐쇄된다면, 압도적인 힘으로 인해 죽게 될 것이다. 처참하게.

킹민성은 이와 같은 사실을 방에서 컴퓨터를 찾은 당신에게 전하고 도움을 구했다. 킹민성과 친구들을 모두 무사히 탈출시키자!

Input

첫째 줄에는 N ( 1<=N<=100 ), P ( 1<=P<=N ), Q ( 1<=Q<=N )가 주어진다. N은 방의 개수, P는 킹민성과 친구들의 총 수, Q는 탈출 가능한 방의 수를 나타낸다.
둘째 줄에는 킹민성과 각 친구들이 0분에 위치한 방의 번호들이 주어진다.
셋째 줄에는 탈출 가능한 방의 번호들이 주어진다.
넷째 줄부터 N+2번째 줄까지 통로 Ai, Bi, Ti ( 1 <=Ai, Bi, Ti<=N )가 주어진다. 통로는 Ai번 방과 Bi번 방을 이으며, Ti분 이후로는 폐쇄된다.

Output

킹민성과 다른 친구들이 모두 탈출할 수 있는 최소 시간(분)을 출력한다. 만약 모두 탈출할 수가 없다면, -1을 출력한다.

IO Example

sample input
8 2 2
3 5
6 7
1 3 1
4 1 3
4 8 3
8 2 4
8 7 5
2 6 4
7 5 1

sample output
4

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