본문 바로가기

Algorithm

(C++) - 백준(BOJ) 1761번 : 정점들의 거리 답

반응형

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

}