문제
풀이
다익스트라 알고리즘에 배운 문제이다. 최소 비용을 구하는 알고리즘에는 크게 3가지 ‘다익스트라 알고리즘 : O(E * logN)’, ‘벨만-포드 알고리즘 : O(|V||E|)’, ‘ 플로이드 워샬 알고리즘 : O(V^3)’이 있다고 한다. 인접리스트에 pair로 push_back을 해주어, 간선이 이어진 부분과 value를 넣는다. 그 이후 기본적인 BFS코드를 적용하는데 우선순위큐(기본적으로 최대힙)을 사용한다. cost에 (-)를 붙인 이유는 기본적인 우선순위큐가 앞서 말했듯이 최힙이라서 -을 붙임으로써 크기를 반전시켜 최소값을 빠르게 찾기 위함이다. MAX값을 기본값으로 가지는 dist 배열을 통해 그 지점에 도달한 것들 중에서 비용이 가장 적게든 것을 담게 한 뒤 최종적으로 출력을 해주면 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#define MAX 20010
#define INF 987654321
#define scanf scanf_s
using namespace std;
vector<pair<int,int>> map[MAX];
int dist[MAX];
int V, E;
int start;
void bfs() {
priority_queue<pair<int, int>> q;
q.push(make_pair(0, start));
dist[start] = 0;
while (!q.empty()) {
int cost = -q.top().first;
int dest = q.top().second;
q.pop();
for (int i = 0; i < map[dest].size(); i++) {
int next_dest = map[dest][i].first;
int next_cost = map[dest][i].second;
if (dist[next_dest] > cost + next_cost) {
dist[next_dest] = cost + next_cost;
q.push(make_pair(-dist[next_dest], next_dest));
}
}
}
for (int i = 1; i <= V; i++)
{
if (dist[i] == INF) printf("INF\n");
else printf("%d\n", dist[i]);
}
}
int main() {
scanf("%d %d", &V, &E);
scanf("%d", &start);
for (int i = 0; i < E; i++) {
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
map[u].push_back(make_pair(v, w));
}
for (int i = 1; i <= V; i++) {
dist[i] = INF;
}
bfs();
}
