티스토리 뷰

알고리즘 관련/BOJ

BOJ)8012 한동이는 영업사원!

JASON 자손9319 2017. 1. 25. 18:24

문제:icpc.me/8012


한동이가 방문해야 할 도시를 x->y->z->w 순이라면 


x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다.


결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 


우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다.


x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다.


이를 이용하여 답을 구해주면 된다.


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
59
60
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_N 30000
using namespace std;
int n, m, visited[MAX_N + 1], dph[MAX_N + 1], par[MAX_N + 1][20], x, y, r;
vector<vector<int>>vt;
void dfs(int v, int d) {
    visited[v] = true;
    dph[v] = d;
    for (auto next : vt[v]) {
        if (visited[next])
            continue;
        par[next][0= v;
        dfs(next, d + 1);
    }
}
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"&x, &y);
        vt[x].push_back(y);
        vt[y].push_back(x);
    }
    dfs(10);
    f();
    y = 1;
    scanf("%d"&m);
    for (int i = 0; i < m; i++) {
        scanf("%d"&x);
        int qlca = lca(x, y);
        r += dph[x] + dph[y] - * dph[qlca];
        y = x;
    }
    printf("%d\n", r);
    return 0;
}
cs


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

BOJ)2211 네트워크 복구  (0) 2017.01.26
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
TAG
,
댓글
댓글쓰기 폼