[BOJ 20894] Brobygge

체감 난이도: Platinum IV + 0.2

 

태그

• Sparse Table (희소 배열)
• Lowest Common Ancestor (최소 공통 조상)

 

풀이

1. \( E = 0 \)이면?

잘 알려진 문제입니다.

 

\( d[v] = \) \( 1 \)번 정점부터 \( v \)번 정점까지의 길이, \( l = \text{lca}(v, w) \)라고 할 때

\( \text{dis}(v, w) = \text{dis}(v, l) + \text{dis}(l, w) = d[v]-d[l] + d[w]-d[l] \)입니다.

 

그러니, \( d[v] \)를 전처리한 후 LCA를 빠르게 구하기 위한 희소 배열까지 만들어주면 됩니다.

 

2. 추가된 간선을 반드시 타야 한다면?

추가된 간선이 \( v_1 \)번 정점과 \( w_1 \)번 정점을 잇는 길이 \( x_1 \)의 간선이라고 합시다.

그럼, \( s \)에서 시작해서 \( t \)로 가는 경로는 \( s \Rightarrow v_1 \rightarrow w_1 \Rightarrow t \)로 표현할 수 있습니다.

이 때의 최단 경로는 \( \text{dis}(s, v_1) + x_1 + \text{dis}(w_1, t) \)가 됩니다.

 

사실 정확히는 \( s \Rightarrow w_1 \rightarrow v_1 \Rightarrow t \)도 고려해줘야 합니다. 결과는 (같지는 않지만) 비슷하게 나오니 패스하겠습니다.

 

간선이 2개여도, \( s \Rightarrow v_1 \rightarrow w_1 \Rightarrow v_2 \rightarrow w_2 \Rightarrow t \)를 사용하면 됩니다.

이 때의 최단 경로는 \( \text{dis}(s, v_1) + x_1 + \text{dis}(w_1, v_2) + x_2 + \text{dis}(w_2, t) \)가 됩니다.

 

위와 비슷하게, 간선 2개를 타는 경우를 다 따지려면 총 8가지 경우가 있습니다. 코드에서 구경해볼 수 있습니다.

 

실제로는 반드시 타야 할 필요는 없으므로,

반드시 탈 때와 그렇지 않을 때 중 더 작은 값을 골라주면 됩니다.

 

코드

구현의 편의성을 위해, \( E = 2 \)로 고정한 대신 존재하지 않는 간선은 길이를 충분히 크게 잡았습니다.

vector<pi2> adj[100020];
 
const int B = 17;
int spr[20][100020];
int dep[100020]; ll dis[100020];
 
void dfs(int now, int pre){
    for (pi2 p : adj[now]){
        int nxt = p.fr, dst = p.sc;
        if (nxt == pre){ continue; }
        spr[0][nxt] = now; dep[nxt] = dep[now]+1; dis[nxt] = dis[now]+dst;
        dfs(nxt, now);
    }
}
 
int lca(int v, int w){
    if (dep[v] > dep[w]){ swap(v, w); }
    int dif = dep[w]-dep[v];
    for (int b = B; b >= 0; b--){
        if (dif>>b & 1){ w = spr[b][w]; }
    }
    if (v==w){ return v; }
    for (int b = B; b >= 0; b--){
        if (spr[b][v] != spr[b][w]){ v = spr[b][v]; w = spr[b][w]; }
    }
    return spr[0][v];
}
inline ll f(int v, int w){
    int l = lca(v, w); return dis[v]-dis[l] + dis[w]-dis[l];
}
 
pi3 edg[3];
 
void Main(){
    int n; cin >> n;
    for (int i = 1; i < n; i++){
        int v, w, x; cin >> v >> w >> x; v++; w++;
        adj[v].push_back({w, x}); adj[w].push_back({v, x});
    }
    dep[1] = dis[1] = 0; spr[0][1] = 1; dfs(1, 1);
    for (int b = 1; b <= B; b++){
        for (int v = 1; v <= n; v++){
            spr[b][v] = spr[b-1][ spr[b-1][v] ];
        }
    }
    int e; cin >> e;
    int v1 = 1, w1 = 1; ll x1 = 1e15;
    int v2 = 1, w2 = 1; ll x2 = 1e15;
    if (1 <= e){ cin >> v1 >> w1 >> x1; v1++; w1++; }
    if (2 <= e){ cin >> v2 >> w2 >> x2; v2++; w2++; }
    int q; cin >> q; while (q--){
        int v, w; cin >> v >> w; v++; w++;
        cout << min({
            f(v,w),
            f(v,v1)+x1+f(w1,w),
            f(v,w1)+x1+f(v1,w),
            f(v,v2)+x2+f(w2,w),
            f(v,w2)+x2+f(v2,w),
            f(v,v1)+x1+f(w1,v2)+x2+f(w2,w),
            f(v,v1)+x1+f(w1,w2)+x2+f(v2,w),
            f(v,w1)+x1+f(v1,v2)+x2+f(w2,w),
            f(v,w1)+x1+f(v1,w2)+x2+f(v2,w),
            f(v,v2)+x2+f(w2,v1)+x1+f(w1,w),
            f(v,v2)+x2+f(w2,w1)+x1+f(v1,w),
            f(v,w2)+x2+f(v2,v1)+x1+f(w1,w),
            f(v,w2)+x2+f(v2,w1)+x1+f(v1,w),
        }) << endl;
    }
}