백준 11779. 최소비용 구하기2

tose33 2022. 9. 1. 13:14

11779번: 최소비용 구하기 2

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

www.acmicpc.net

하나의 노드에서 다른 노드까지의 최소비용을 구하는 다익스트라 알고리즘을 사용하면 된다.

이 문제는 도착 노드까지의 경로도 출력해야하기 때문에 다익스트라 알고리즘에서 우선순위큐에 보통 {거리, 노드}를 삽입하는데 대신 {거리, 현재까지 방문 노드들 담긴 벡터}를 넣어주면 된다.