코딩스토리

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘 관련 문제이다. 처음 봤을 때 어떻게 해야 할지 감은 잡혔으나 그걸 코드로 옮기는 게 너무 어려웠다.. 먼저 떠올렸던 해법은 1. 다익스트라를 통해 시작점부터 도착점까지 최단 거리를 구한다. 2. 최단 경로에 포함된 간선들을 모두 제거한다. 3. 다익스트라를 통해 거의 최단 경로를 구한다. 문제는 2번이였다. 최단 경로가 여러 개가 나올 수 있고, 그렇다면 그 ..