출처 : 백준
문제 보러가기 : 최단경로
해당 문제는 방향 그래프에서 특정 정점에 대해서 각 정점에 대한 최단 거리를 구하는 문제이다.
BFS, Bellman-Ford 등 최단경로를 찾는 여러 알고리즘이 있지만 해당 문제는 양의 간선만 존재하기 때문에 Dijkstra알고리즘을 선택하였다.
Dijkstra알고리즘은 정점의 수를 V라 할때 O(V^2)의 시간복잡도를 가지고 있으며 우선순위큐를 이용한다면 좀 더 나은 성능을 발휘할 수 있다.
C++ STL의 priority_queue를 이용하였다. 최단거리를 구하는 문제이므로 작은 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
71
72
73
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 30000001
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int v, l, x, s, e, w;
int len;
vector<int> dist;
vector<pair<int, int>> con[20001];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
cin >> v >> l;
cin >> x;
for (int i = 0; i < l; i++)
{
cin >> s >> e >> w;
con[s].push_back({w, e});
}
dist.resize(v + 1);
for (int i = 1; i <= v; i++)
{
dist[i] = INF;
}
dist[x] = 0;
pq.push({0, x});
while (!pq.empty())
{
int cdist = pq.top().first;
int cnode = pq.top().second;
pq.pop();
if (dist[cnode] < cdist)
continue;
for (int i = 0; i < con[cnode].size(); i++)
{
int nnode = con[cnode][i].second;
int ndist = cdist + con[cnode][i].first;
if (dist[nnode] > ndist)
{
dist[nnode] = ndist;
pq.push({ndist, nnode});
}
}
}
for (int i = 1; i < dist.size(); i++)
{
if (dist[i] == INF)
cout << "INF\n";
else
cout << dist[i] << "\n";
}
return 0;
}
|
cs |
댓글