11779

[백준 11779] 최소 비용 구하기 2 C++

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 A 도시에서 B 도시로 가는 최소 비용을 알아야 한다. 간선의 비용은 음수가 없다. 위 두가지 정보로 다익스트라문제인걸 알았다. 다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다. bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다. 예시 입력을 그래프로 나타냈다. 1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2,..