백준 다익스트라 c++

[baekjoon 2307] 도로검문 (다익스트라) (C++)

https://www.acmicpc.net/problem/2307 2307번: 도로검문 그림 1은 어떤 도시의 주요 지점과 그 지점들 간의 이동시간을 나타낸 그래프이다. 그래프의 노드는 주요 지점을 나타내고 두 지점을 연결한 도로(에지)에 표시된 수는 그 도로로 이동할 때 걸 www.acmicpc.net 용의자가 주어진 그래프를 빠져나가려는데, 그래프 중 하나의 간선을 막아서 얼마나 지연시킬 수 있는지 출력하는 문제이다. 구역은 최대 1000개, 간선의 개수는 최대 5000개가 주어진다. 따라서 완전 탐색으로 모든 도로를 지우며 비교하는 것은 시간 초과가 날 것이다. 우선 1번부터 N번까지 최단 거리를 구해야 하므로 다익스트라를 이용하고, 최단 거리가 나오는 경로를 구해서 그 경로에 해당하는 도로만 지우..