forked from ndb796/python-for-coding-test
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path4.cpp
More file actions
77 lines (67 loc) ยท 2.65 KB
/
4.cpp
File metadata and controls
77 lines (67 loc) ยท 2.65 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
#include <bits/stdc++.h>
#define INF 1e9 // ๋ฌดํ์ ์๋ฏธํ๋ ๊ฐ์ผ๋ก 10์ต์ ์ค์
using namespace std;
// ๋
ธ๋์ ๊ฐ์(N), ๊ฐ์ ์ ๊ฐ์(M)
int n, m;
// ์์ ๋
ธ๋๋ฅผ 1๋ฒ ํ๊ฐ์ผ๋ก ์ค์
int start = 1;
// ๊ฐ ๋
ธ๋์ ์ฐ๊ฒฐ๋์ด ์๋ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๋ด๋ ๋ฆฌ์คํธ๋ฅผ ๋ง๋ค๊ธฐ
vector<pair<int, int> > graph[20001];
// ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ ๋ง๋ค๊ธฐ
int d[20001];
void dijkstra(int start) {
priority_queue<pair<int, int> > pq;
// ์์ ๋
ธ๋๋ก ๊ฐ๊ธฐ ์ํ ์ต๋จ ๊ฒฝ๋ก๋ 0์ผ๋ก ์ค์ ํ์ฌ, ํ์ ์ฝ์
pq.push({0, start});
d[start] = 0;
while (!pq.empty()) { // ํ๊ฐ ๋น์ด์์ง ์๋ค๋ฉด
// ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ์งง์ ๋
ธ๋์ ๋ํ ์ ๋ณด๋ฅผ ๊บผ๋ด๊ธฐ
int dist = -pq.top().first; // ํ์ฌ ๋
ธ๋๊น์ง์ ๋น์ฉ
int now = pq.top().second; // ํ์ฌ ๋
ธ๋
pq.pop();
// ํ์ฌ ๋
ธ๋๊ฐ ์ด๋ฏธ ์ฒ๋ฆฌ๋ ์ ์ด ์๋ ๋
ธ๋๋ผ๋ฉด ๋ฌด์
if (d[now] < dist) continue;
// ํ์ฌ ๋
ธ๋์ ์ฐ๊ฒฐ๋ ๋ค๋ฅธ ์ธ์ ํ ๋
ธ๋๋ค์ ํ์ธ
for (int i = 0; i < graph[now].size(); i++) {
int cost = dist + graph[now][i].second;
// ํ์ฌ ๋
ธ๋๋ฅผ ๊ฑฐ์ณ์, ๋ค๋ฅธ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ฑฐ๋ฆฌ๊ฐ ๋ ์งง์ ๊ฒฝ์ฐ
if (cost < d[graph[now][i].first]) {
d[graph[now][i].first] = cost;
pq.push({-cost, graph[now][i].first});
}
}
}
}
int main(void) {
cin >> n >> m;
// ๋ชจ๋ ๊ฐ์ ์ ๋ณด๋ฅผ ์
๋ ฅ๋ฐ๊ธฐ
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
// a๋ฒ ๋
ธ๋์ b๋ฒ ๋
ธ๋์ ์ด๋ ๋น์ฉ์ด 1์ด๋ผ๋ ์๋ฏธ(์๋ฐฉํฅ)
graph[a].push_back({b, 1});
graph[b].push_back({a, 1});
}
// ์ต๋จ ๊ฑฐ๋ฆฌ ํ
์ด๋ธ์ ๋ชจ๋ ๋ฌดํ์ผ๋ก ์ด๊ธฐํ
fill(d, d + 20001, INF);
// ๋ค์ต์คํธ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ํ
dijkstra(start);
// ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ๋
ธ๋ ๋ฒํธ(๋๋น์ด๊ฐ ์จ์ ํ๊ฐ์ ๋ฒํธ)
int maxNode = 0;
// ๋๋ฌํ ์ ์๋ ๋
ธ๋ ์ค์์, ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ๋
ธ๋์์ ์ต๋จ ๊ฑฐ๋ฆฌ
int maxDistance = 0;
// ๊ฐ์ฅ ์ต๋จ ๊ฑฐ๋ฆฌ๊ฐ ๋จผ ๋
ธ๋์์ ์ต๋จ ๊ฑฐ๋ฆฌ์ ๋์ผํ ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๊ฐ์ง๋ ๋
ธ๋๋ค์ ๋ฆฌ์คํธ
vector<int> result;
for (int i = 1; i <= n; i++) {
if (maxDistance < d[i]) {
maxNode = i;
maxDistance = d[i];
result.clear();
result.push_back(maxNode);
}
else if (maxDistance == d[i]) {
result.push_back(i);
}
}
cout << maxNode << ' ' << maxDistance << ' ' << result.size() << '\n';
}