고고학자 철수는 악어의 신비한 지하 도시를 탐험하다가 위험을 느끼고 도망치게 되었다. 지하 도시는 N 개의 방으로 구성되어 있다. 방들을 연결하는 M 개의 복도가 있는데, 각 복도는 서로 다른 두 방을 연결하며, 같은 쌍의 방을 연결하는 복도는 최대 1 개이다. 복도를 통과하는데 걸리는 시간은 복도마다 다를 수 있다. N 개의 방들 중 K 개는 바로 탈출이 가능한 “탈출방”이다. 철수는 최초에 방 0 에 있다. 철수는 최대한 빨리 탈출방으로 가려고 다. 악어 문지기는 철수가 탈출하는 것을 막으려고 한다. 문지기는 복도 중 임의의 하나를 막을 수 있는 방법이 있다. 어떤 시점이든 단 하나만 막을 수 있다. 즉, 문지기가 새로운 복도를 막으면 이전에 막았던 복도는 열린다.
철수의 상황을 좀더 자세히 설명하면 다음과 같다: 철수가 어떤 방을 떠나려고 때 문지기는 그 방과 연결된 복도들 중 하나를 막을 수 있다. 철수는 막히지 않은 복도 중 하나를 골라서 다른 방으로 이동한다. 철수가 복도에 일단 들어가고 나면 철수가 이동을 완료할 때 까지는 문지기가 이 복도를 막을 수 없다. 철수가 다른 방에 들어가고 나면 문지기는 (방금 지나온 복도도 당연히 포함하여) 또 다른 복도를 막을 수 있고, 이런 식으로 반복된다.
철수는 탈출 계획을 미리 정해 놓기를 원한다. 정확히 말하자면, 각 방 마다, 그 방에 도착하면 어떤 식으로 행동해야 하는 지의 계획이 미리 정해져 있어야 한다.
A 가 어떤 방이라고 하자. 만약 A 가 탈출방이라면 바로 탈출하면 되므로 별다른 계획이 필요하지 않다.
A 가 탈출방이 아니라면 A 에 대해서는 다음 중 한가지 형태의 계획이 있어야 다.
어떤 탈출 계획이 문지기가 어떤 작전을 쓰던지 철수가 유한한 시간안에 탈출하는 것이 가능하다는 것을 보장하면 그 계획은 "좋은" 계획이라고 부른다. 어떤 좋은 계획 하에서, 철수가 그 시간이 지난 후에는 반드시 탈출한다고 보장할 수 있는 최소의 시간을 T 라고 하자. 그 경우, 그 좋은 계획의 “탈출 시간”은 T 라고 말한다.
제한 시간은 2 초이다.
입력 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
방들은 원으로 표시되었고 복도는 줄로 표시되어 있다. 탈출방들은 굵은 원으로 표시되어 있다. 초기에 철수는 (삼각형으로 표시된) 방 0 에 있다. 최적의 탈출 계획 중 하나는 다음과 같다.
입출력예 2.
가능한 최적의 계획들 중 하나는 다음과 같다.
출처:ioi 2011 day2 1/3