티스토리 뷰

알고리즘 관련/BOJ

BOJ)1761 정점들의 거리

JASON 자손9319 2017. 1. 25. 17:42

문제:icpc.me/1761


두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다.


우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다.


하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다.


우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다.


lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면


두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다.


이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 40000
using namespace std;
int n, m, visited[MAX_N + 1], dph[MAX_N + 1], par[MAX_N + 1][20], dist[MAX_N + 1], x, y, z;
vector<vector<pair<intint>>>vt;
void dfs(int v, int dh, int dis) {
    visited[v] = true;
    dph[v] = dh;
    dist[v] = dis;
    for (auto u : vt[v]) {
        if (visited[u.first])
            continue;
        dfs(u.first, dh + 1, dis + u.second);
        par[u.first][0= v;
    }
}
void f() {
    for (int j = 1; j < 20; j++) {
        for (int i = 1; i <= n; i++
            par[i][j] = par[par[i][j - 1]][j - 1];
    }
}
int lca(int x, int y) {
    if (dph[x] > dph[y])
        swap(x, y);
    for (int i = 19; i >= 0; i--) {
        if (dph[y] - dph[x] >= (<< i))
            y = par[y][i];
    }
    if (x == y)return x;
    for (int i = 19; i >= 0; i--) {
        if (par[x][i] != par[y][i]) {
            x = par[x][i];
            y = par[y][i];
        }
    }
    return par[x][0];
}
int main() {
    scanf("%d"&n);
    vt.resize(n + 1);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d%d"&x, &y, &z);
        vt[x].push_back({ y,z });
        vt[y].push_back({ x,z });
    }
    dfs(100);
    f();
    scanf("%d"&m);
    while (m--) {
        scanf("%d%d"&x, &y);
        int qlca = lca(x, y);
        printf("%d\n", dist[x] + dist[y] - * dist[qlca]);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2275 트리의 높이 줄이기  (0) 2017.01.25
BOJ)8012 한동이는 영업사원!  (2) 2017.01.25
BOJ)1761 정점들의 거리  (0) 2017.01.25
BOJ)2512 예산  (0) 2017.01.25
BOJ)1576 DNA점수  (0) 2017.01.25
BOJ)10265 MT  (0) 2017.01.24
TAG
,
댓글
댓글쓰기 폼