동현이는 최단거리(경로) 알고리즘를 연구하고 있다. 자동차 네비게이션과 도로 지도 등 여러 곳에 응용분야가 많다고 들었기 때문이다. 최근, 연구 중에 아주 놀라운 점을 하나 발견하였는데 최단거리가 최단시간을 의미하지 않는다는 것이었다.

거리는 조금 멀더라도 시간은 최단 거리보다 덜 걸리는 경우가 종종 있었다.

그래서 동현이는 최단 거리는 아니지만 최단 거리에 가까운 경로에 관심을 가지게 되었다.

동현이는 최단 거리에 가까운 경로를 거의 최단 경로라 명명하고 그 정의를 “최단 경로에 포함되지 않는 경로들만으로 이루어진 가장 짧은 경로”라고 정했다.

예를 들어 도로 지도를 그래프 형태로 나타낸 아래 그림을 보자. 원은 특정장소를 나타내고 화살표는 일방통행 도로를 나타낸다. 아래 그림에서 굵은 실선은 최단경로로서 이 그림에서는 두 가지가 나온다. 점선은 거의 최단경로로서 최단 경로에 포함되지 않는 경로로 이루어진 가장 짧은 경로이다. 짐작하겠지만 거의 최단 경로는 여러 가지가 나올 수도 있고 경로가 없을 수도 있다.

지도 정보가 주어질 때 거의 최단 경로를 구하는 프로그램을 작성하시오.

#3050 upload 129 done 32 how_to_reg 17

거의 최단 경로 timer 1s memory 128MB

#3050

거의 최단 경로 1s 128MB