문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 풀이 solved.ac 난이도: Platium 5 다익스트라는 기본적으로 최단 경로 값만 구하기 때문에 동일한 최단 경로가 여러 개가 있더라도 결국 하나의 값만 저장이 된다. 이번 문제는 최단 경로들에 사용된 모든 간선을 사용하지 않고(사실상 제거하고) 최단 경로를 구하는 것이다. 따라서 정점들의 각각에 우선순위 큐를 사용하여 해당 정점에 최소 cost으로 도달..