문제 풀이
priority queue를 이용한 다익스트라 알고리즘을 사용하는 문제입니다. 노드의 수가 매우 많기 때문에 메모리를 줄이기 위하여 간선을 저장하였습니다. 단방향 그래프이기 때문에, 출발 노드와 도착 노드 중 출발 노드에만 간선을 저장해 주었습니다. check 배열에는 해당 노드를 방문한 적이 있는지 알아보았고, road 배열에는 최단 거리를 저장해주었습니다. 재방문하게 되는 경우, 최단 거리를 갱신하면서 탐색을 진행합니다.
다익스트라 알고리즘에 대해서 반드시 알아야 풀 수 있었던 문제라, 한 번 알아보시면 도움이 될 것 같습니다!
코드
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;
const int MAX = 999999;
int ans;
bool check[20001];
int road[20001];
vector <pair<int, int>> g[20001];
void bfs(int a) {
memset(check, false, sizeof(check));
memset(road, MAX, sizeof(road));
priority_queue <pair<int, int>, vector< pair<int,int> >, greater< pair<int, int> > > q;
q.emplace(0, a);
road[a] = 0;
check[a] = true;
while (!q.empty()) {
pair<int, int> x;
x = q.top();
q.pop();
for (int i = 0; i < g[x.second].size(); i++) {
if (check[g[x.second][i].first] == false || road[g[x.second][i].first] > x.first + g[x.second][i].second)
{
check[g[x.second][i].first] = true;
road[g[x.second][i].first] = x.first + g[x.second][i].second;
q.emplace(x.first + g[x.second][i].second, g[x.second][i].first);
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, e, s;
cin >> n >> e >> s;
for (int i = 1; i <= e; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].emplace_back(v, w);
}
bfs(s);
for (int k = 1; k <= n; k++) {
if (!check[k])
cout << "INF\n";
else
cout << road[k] << '\n';
}
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
|
제출 결과
문제 출처
https://www.acmicpc.net/problem/1753
'algorithm codes > baekjoon online judge' 카테고리의 다른 글
9655번: 돌게임 (백준 온라인 저지, C++) (0) | 2019.05.24 |
---|---|
16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++) (0) | 2019.05.07 |
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++) (0) | 2019.05.01 |
17143번: 낚시왕 (백준 온라인 저지, C++) (0) | 2019.04.30 |
3053번: 택시 기하학 (0) | 2019.04.27 |