[백준][BOJ11779] 최소비용 구하기 2

Algorithm/Dijkstra

by bedamino 2021. 7. 14. 21:45

1. 문제 : https://www.acmicpc.net/problem/11779

11779번: 최소비용 구하기 2

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스

www.acmicpc.net

2. 풀이 : 다익스트라

3. 설명

그림[1]에서 도착점인 5번 노드까지의 최단 경로는 다익스트라의 구현 방법에 따라 1->3->5 혹은 1->4->5 2가지의 최단 경로가 가능하다. 경로 추적 배열은 출발점인 1번 노드는 -1로 갱신하고, 각 노드의 최단 거리가 갱신되는 시점에 갱신한다. 최단 경로를 다 찾은 후, 도착점부터 출발점까지 경로를 역추적하여 방문하는 도시 순서대로 출력할 수 있다.

4. 코드