알고리즘
- BFS로 시작 정점부터, 이제까지 경로 중에 있었던 가장 큰 weight(bigest)와 이제까지의 weight를 모두 합한 값(length)을 저장해나가며 진행.
- 이때 visit을 표시할 때, true/false 값이 아닌, length을 저장.
- BFS를 진행할 땐, node에 저장된 length와 현재 로봇의 length와 그 통로의 weight를 합한 값이 작을때만 진행.
- 3을 위해서는 visit 배열을 큰 값으로 초기화해야함.
코드
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
#include <bits/stdc++.h>
using namespace std;
struct robot {
int bigest;
int cur;
int length;
};
vector<pair<int,int>> edges[100010];
int n, a, b;
int nodes[100010];
list<robot> q;
int BFS();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> a >> b;
for (int i = 0; i < n-1; i++) {
int t1, t2, t3;
cin >> t1 >> t2 >> t3;
edges[t1].push_back({ t2, t3 });
edges[t2].push_back({ t1, t3 });
}
for (int i = 1; i <=n; i++) {
nodes[i] = 2000000000;
}
cout << BFS() << "\n";
}
int BFS() {
q.push_back({ 0, a, 0});
nodes[a] = 0;
int result = 2000000000;
while (!q.empty()) {
int cur = q.front().cur, bigest = q.front().bigest, length = q.front().length;
q.pop_front();
if (cur == b) {
result = min(result, length - bigest);
continue;
}
for (int i = 0; i < edges[cur].size(); i++) {
int to = edges[cur][i].first, w = edges[cur][i].second;
if (length + w < nodes[to]) {
int bigger = max(bigest, w);
nodes[to] = length + w;
q.push_back({ bigger, to, nodes[to] });
}
}
}
return result;
}