์•Œ๊ณ ๋ฆฌ์ฆ˜

  1. BFS๋กœ ์‹œ์ž‘ ์ •์ ๋ถ€ํ„ฐ, ์ด์ œ๊นŒ์ง€ ๊ฒฝ๋กœ ์ค‘์— ์žˆ์—ˆ๋˜ ๊ฐ€์žฅ ํฐ weight(bigest)์™€ ์ด์ œ๊นŒ์ง€์˜ weight๋ฅผ ๋ชจ๋‘ ํ•ฉํ•œ ๊ฐ’(length)์„ ์ €์žฅํ•ด๋‚˜๊ฐ€๋ฉฐ ์ง„ํ–‰.
  2. ์ด๋•Œ visit์„ ํ‘œ์‹œํ•  ๋•Œ, true/false ๊ฐ’์ด ์•„๋‹Œ, length์„ ์ €์žฅ.
  3. BFS๋ฅผ ์ง„ํ–‰ํ•  ๋•, node์— ์ €์žฅ๋œ length์™€ ํ˜„์žฌ ๋กœ๋ด‡์˜ length์™€ ๊ทธ ํ†ต๋กœ์˜ weight๋ฅผ ํ•ฉํ•œ ๊ฐ’์ด ์ž‘์„๋•Œ๋งŒ ์ง„ํ–‰.
  4. 3์„ ์œ„ํ•ด์„œ๋Š” visit ๋ฐฐ์—ด์„ ํฐ ๊ฐ’์œผ๋กœ ์ดˆ๊ธฐํ™”ํ•ด์•ผํ•จ.

์ฝ”๋“œ

#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;
}