forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path1.cpp
More file actions
80 lines (71 loc) ยท 2.57 KB
/
1.cpp
File metadata and controls
80 lines (71 loc) ยท 2.57 KB
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
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define INF 1e9 // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์
using namespace std;
// ๋
ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M), ์์ ๋
ธ๋ ๋ฒํธ(Start)
// ๋
ธ๋์ ๊ฐ์๋ ์ต๋ 100,000๊ฐ๋ผ๊ณ ๊ฐ์
int n, m, start;
// ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฐฐ์ด
vector<pair<int, int> > graph[100001];
// ๋ฐฉ๋ฌธํ ์ ์ด ์๋์ง ์ฒดํฌํ๋ ๋ชฉ์ ์ ๋ฐฐ์ด ๋ง๋ค๊ธฐ
bool visited[100001];
// ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ๋ง๋ค๊ธฐ
int d[100001];
// ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋์ ๋ฒํธ๋ฅผ ๋ฐํ
int getSmallestNode() {
int min_value = INF;
int index = 0; // ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋(์ธ๋ฑ์ค)
for (int i = 1; i <= n; i++) {
if (d[i] < min_value && !visited[i]) {
min_value = d[i];
index = i;
}
}
return index;
}
void dijkstra(int start) {
// ์์ ๋
ธ๋์ ๋ํด์ ์ด๊ธฐํ
d[start] = 0;
visited[start] = true;
for (int j = 0; j < graph[start].size(); j++) {
d[graph[start][j].first] = graph[start][j].second;
}
// ์์ ๋
ธ๋๋ฅผ ์ ์ธํ ์ ์ฒด n - 1๊ฐ์ ๋
ธ๋์ ๋ํด ๋ฐ๋ณต
for (int i = 0; i < n - 1; i++) {
// ํ์ฌ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๊ฐ์ฅ ์งง์ ๋
ธ๋๋ฅผ ๊บผ๋ด์, ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ
int now = getSmallestNode();
visited[now] = true;
// ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ๋
ธ๋๋ฅผ ํ์ธ
for (int j = 0; j < graph[now].size(); j++) {
int cost = d[now] + graph[now][j].second;
// ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ์ ๋ค๋ฅธ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ
if (cost < d[graph[now][j].first]) {
d[graph[now][j].first] = cost;
}
}
}
}
int main(void) {
cin >> n >> m >> start;
// ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
// a๋ฒ ๋
ธ๋์์ b๋ฒ ๋
ธ๋๋ก ๊ฐ๋ ๋น์ฉ์ด c๋ผ๋ ์๋ฏธ
graph[a].push_back({b, c});
}
// ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ
fill_n(d, 100001, INF);
// ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
dijkstra(start);
// ๋ชจ๋ ๋
ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
for (int i = 1; i <= n; i++) {
// ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ, ๋ฌดํ(INFINITY)์ด๋ผ๊ณ ์ถ๋ ฅ
if (d[i] == INF) {
cout << "INFINITY" << '\n';
}
// ๋๋ฌํ ์ ์๋ ๊ฒฝ์ฐ ๊ฑฐ๋ฆฌ๋ฅผ ์ถ๋ ฅ
else {
cout << d[i] << '\n';
}
}
}