PS/BOJ
백준 3176번: 도로 네트워크 (C++)
도비(Doby)
2022. 5. 3. 22:11
https://www.acmicpc.net/problem/3176
3176번: 도로 네트워크
첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양
www.acmicpc.net
Solved By: LCA
바로 직전의 포스팅 문제 (1761)과 비슷합니다. 거리의 점화식을 사용하여 구할 수 있습니다.
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#define MAX 100001
#define LOG_MAX 18
#define pii pair<int, int>
using namespace std;
int n, k;
int parent[MAX][LOG_MAX];
int minRoad[MAX][LOG_MAX], maxRoad[MAX][LOG_MAX];
int level[MAX];
vector<pii> adj[MAX];
void dfs(int now, int par){
for(int i = 0; i < adj[now].size(); i++){
int next = adj[now][i].first;
int cost = adj[now][i].second;
if(next == par) continue;
parent[next][0] = now;
level[next] = level[now] + 1;
minRoad[next][0] = maxRoad[next][0] = cost;
dfs(next, now);
}
}
void swap(int *a, int *b){
int* temp = a;
a = b;
b = temp;
}
pii lca(int a, int b){
int maxV = 0, minV = 1e9;
if(level[a] < level[b]) swap(a, b);
int diff = level[a] - level[b];
for(int i = LOG_MAX - 1; i >= 0; i--){
if(diff >= 1 << i){
diff -= 1 << i;
minV = min(minV, minRoad[a][i]);
maxV = max(maxV, maxRoad[a][i]);
a = parent[a][i];
}
}
if(a != b){
for(int i = LOG_MAX - 1; i >= 0; i--){
if(parent[a][i] != 0 && parent[a][i] != parent[b][i]){
minV = min(minV, minRoad[a][i]);
minV = min(minV, minRoad[b][i]);
maxV = max(maxV, maxRoad[a][i]);
maxV = max(maxV, maxRoad[b][i]);
a = parent[a][i];
b = parent[b][i];
}
}
minV = min(minV, minRoad[a][0]);
minV = min(minV, minRoad[b][0]);
maxV = max(maxV, maxRoad[a][0]);
maxV = max(maxV, maxRoad[b][0]);
}
return {minV, maxV};
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i = 0; i < n - 1; i++){
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b, c});
adj[b].push_back({a, c});
}
dfs(1, 0);
for(int j = 1; j < LOG_MAX; j++){
for(int i = 1; i <= n; i++){
parent[i][j] = parent[parent[i][j - 1]][j - 1];
minRoad[i][j] = min(minRoad[parent[i][j - 1]][j - 1], minRoad[i][j - 1]);
maxRoad[i][j] = max(maxRoad[parent[i][j - 1]][j - 1], maxRoad[i][j - 1]);
}
}
cin >> k;
while(k--){
int a, b; cin >> a >> b;
cout << lca(a, b).first << ' ' << lca(a, b).second << '\n';
}
return 0;
}