Baekjoon 1761 정점들의 거리
2019. 4. 22.
Link https://www.acmicpc.net/problem/1761 소스결과 6504 KB / 668 ms 언어 C++ 17 출처 Baekjoon 분류 LCA 설명 가중치가 있는 트리가 주어질 때 두 정점 사이의 가중치의 합을 출력한다. 기존 LCA문제에서 가중치가 추가된 LCA문제. 단지 루트 노드가 지정이 되지 않았기에 어느 노드를 기준으로 깊이를 설정해도 상관은 없다. 가장 일반적이게 1번 노드를 기준으로 깊이를 지정했다. 두 정점이 주어졌을 때 두 정점의 깊이를 맞추는 과정에서도 가중치의 합을 구해야 하는 것을 조심 해야한다. 두 정점의 깊이가 일치해 졌다면 같은 공통 조상까지 찾아가면서 가중치의 합을 구하면 최소 거리가 된다. 알고리즘 1. 간선과 가중치 정보를 입력 받는다. 2. 임의의..
