반응형
Lowest Common Ancestor(LCA)문제입니다
//트리상에서의 최단거리는 두 정점 사이의 거리이다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m, u, v,cost,ans;
int c[40001],depth[40001],dist[40001],parent[40001];
struct Edge {
int to;
int cost;
Edge(int to, int cost) : to(to), cost(cost) {};
};
vector <Edge> a[40001];//간선의 정점간의 가중치를 저장
queue <int> q;//큐 생성
int lca(int u, int v)
{
if (depth[u] < depth[v])
swap(u, v);
while (depth[u] != depth[v])
{
ans += dist[u];
u = parent[u];
}
while (u != v)
{
ans += dist[u];
ans += dist[v];
u = parent[u];
v = parent[v];
}
return ans;
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++)
{
cin >> u >> v>>cost;
a[u].push_back(Edge(v,cost));
a[v].push_back(Edge(u,cost));
}
c[1] = 1;
q.push(1);
while (!q.empty())
{
int x = q.front();
q.pop();
for (Edge &e:a[x])
{
int y = e.to;
if (!c[y])
{
depth[y] = depth[x] + 1;
dist[y] = e.cost;
parent[y] = x;
c[y] = 1;
q.push(y);
}
}
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> u >> v;
ans = 0;
cout << lca(u, v) <<'\n';
}
}
'Algorithm' 카테고리의 다른 글
(C++) - 백준(BOJ) 6086번 : 최대 유량 답 (0) | 2017.02.24 |
---|---|
(C++) - 백준(BOJ)코딩 10868 : 최소값 답 (0) | 2017.02.24 |
(C++) - 백준(BOJ) 11437번 : 가장 가까운 공통 조상 찾기 답 (0) | 2017.02.24 |
(C++) - 백준(BOJ) 2740번 : 행렬 곱셈 답 (0) | 2017.02.19 |
(C++) - 백준(BOJ) 2738번 : 행렬 덧셈 (0) | 2017.02.19 |