월드산의 하부에는 동굴로 들어가는 입구가 있는데,

동굴은 터널을 통해 서로 연결되어 있는 여러 개의 작은 방들로 구성되어 있다.

동굴 입구는 탐험의 시작점이 되는 방 (이하 시작방)으로 곧장 연결되어 있다.

각 방을 연결하는 터널은 서로 교차하지 않으며, 두 개의 방을 연결하는 터널은 많아 봐야 하나이다.

"원쌤배 동굴 탐험 대회"가 개최될 예정이다.

대회의 목표는 시작방에서 출발하여 동굴 내부를 달려, 다시 시작방으로 되돌아 와 빠져 나오는 것인데,

그 경로는 참가자가 마음대로 정할 수 있지만 두 가지 조건을 지켜야 한다.

첫째 조건은, 시작방 이외의 방을 최소한 하나는 거쳐야 한다는 것이며,

둘째 조건은, 어떤 방과 터널도 최대 한 번밖에 방문할 수 없다는 것이다. (시작방은 물론 두 번 방문하게 되므로 예외이다.)

유명한 동굴 탐험가 김진영은 대회에 참가하기 위해 오랜 준비를 했고,

동굴을 여러 번 사전 답사하여 동굴 내부 구조를 알아내는 데 성공했다.

각각의 터널에 대해, 그는 그 터널을 가로지르는 데 필요한 시간을 계산했는데,

터널을 어느 방향으로 가로지르느냐에 따라 걸리는 시간이 서로 다른 경우도 있을 수 있다고 한다.

동굴 입구와 시작방 사이에서 소요되는 시간이나, 방 내부에서 이동하는데 필요한 시간은 무시할 수 있을 만했다.

이제 그는 경기의 규칙을 만족시키면서도, 가장 짧은 시간 내에 완주할 수 있는 경로를 찾아내려고 한다.

그를 돕기 위한 프로그램을 작성하라.

동굴 탐험 timer 3s memory 1024MB

동굴 탐험 3s 1024MB