Chlience

【题解】CF 1051F The Shortest Statement
Problem传送门 >ω<题目大意:给定一张 $n$ 个点, $m$ 条边的图,其中 $m - n \leq 2...
扫描右侧二维码阅读全文
30
2018/10

【题解】CF 1051F The Shortest Statement

Problem

传送门 >ω<

题目大意:

给定一张 $n$ 个点, $m$ 条边的图,其中 $m - n \leq 20$

给定 $q$ 个询问,每次询问两点之间最短路

Solution

一个很经典的题啦

看起来好像很麻烦的样子,但是只要你知道一个很简单的定理就能轻松A掉

假设图上 $s - t$ 的最短路经过 $k$ ,那么 $dis[s][k] + dis[k][t] = dis[s][t]$

所以说只需要随意构建出一棵树,求出两两之间距离

然后在原图上,以每条没有被构建到树中边的任意一个顶点为原点跑 $Dijkstra$ ,求出 $min(dis[s] + dis[t])$ 即可

时间复杂度 $O((m - n + 1) * n \log n)$

代码略长,请小心食用 qwq

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 100010;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') flag = - flag; ch = getchar();}
    while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}

struct edge {int n , t; LL w;}e[N << 1];
int head[N] , tot;

void addedge(int u , int v , LL w) {
    ++ tot;
    e[tot].t = v;
    e[tot].w = w;
    e[tot].n = head[u];
    head[u] = tot;
}

int n , m , q;
int U[N] , V[N];
LL W[N];
int X[N] , Y[N];
LL ANS[N];
bool vis[N];

void init() {
    n = read(); m = read();
    for(int i = 1 ; i <= m ; ++ i) {U[i] = read(); V[i] = read(); W[i] = read();}
    q = read();
    for(int i = 1 ; i <= q ; ++ i) {X[i] = read(); Y[i] = read();}
}

int F[N];
LL DIS[N][21];
int FA[N][21];

int find(int x) {
    return F[x] == x ? F[x] : F[x] = find(F[x]);
}

int dep[N];
void DFS(int x , int f) {
    dep[x] = dep[f] + 1;
    for(int i = head[x] ; i ; i = e[i].n) {
        if(e[i].t == f) continue;
        FA[e[i].t][0] = x;
        DIS[e[i].t][0] = e[i].w;
        DFS(e[i].t , x);
    }
}
void BZ_prepare() {
    for(int i = 1 ; i <= 20 ; ++ i) {
        for(int j = 1 ; j <= n ; ++ j) {
            FA[j][i] = FA[FA[j][i - 1]][i - 1];
            DIS[j][i] = DIS[j][i - 1] + DIS[FA[j][i - 1]][i - 1];
        }
    }
}
LL lca(int x , int y) {
    LL ans = 0;
    if(dep[x] < dep[y]) swap(x , y);
    for(int i = 20 ; i >= 0 ; -- i)
        if(dep[FA[x][i]] >= dep[y]) {
            ans += DIS[x][i];
            x = FA[x][i];
        }
    if(x == y) return ans;
    for(int i = 20 ; i >= 0 ; -- i) {
        if(FA[x][i] != FA[y][i]) {
            ans += DIS[x][i];
            ans += DIS[y][i];
            x = FA[x][i];
            y = FA[y][i];
        }
    }
    ans += DIS[x][0];
    ans += DIS[y][0];
    return ans;
}
void tree() {
    for(int i = 1 ; i <= n ; ++ i) F[i] = i;
    for(int i = 1 ; i <= m ; ++ i) {
        int fx = find(U[i]);
        int fy = find(V[i]);
        if(fx == fy) vis[U[i]] = 1;
        else {
            F[fx] = fy;
            addedge(U[i] , V[i] , W[i]);
            addedge(V[i] , U[i] , W[i]);
        }
    }
    DFS(1 , 0);
    BZ_prepare();
    for(int i = 1 ; i <= q ; ++ i)
        ANS[i] = lca(X[i] , Y[i]);
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
LL dis[N];
struct TREE {
    LL DIS[N << 2];
    int pos[N << 2];
    void update(int x) {
        if(DIS[L] <= DIS[R]) {
            DIS[x] = DIS[L];
            pos[x] = pos[L];
        }
        else {
            DIS[x] = DIS[R];
            pos[x] = pos[R];
        }
    }
    void build(int x , int l , int r) {
        if(l == r) {
            DIS[x] = LONG_LONG_MAX / 2;
            pos[x] = l;
        }
        else {
            build(L , l , mid);
            build(R , mid + 1 , r);
            update(x);
        }
    }
    void change(int x , int l , int r , int p , LL num) {
        if(l == r) DIS[x] = num;
        else {
            if(p <= mid) change(L , l , mid , p , num);
            else change(R , mid + 1 , r , p , num);
            update(x);
        }
    }
}t;

void dijkstra(int x) {
    for(int i = 1 ; i <= n ; ++ i) dis[i] = LONG_LONG_MAX / 2;
    t.build(1 , 1 , n);
    dis[x] = 0;
    t.change(1 , 1 , n , x , 0);
    for(int i = 1 ; i <= n ; ++ i) {
        x = t.pos[1];
        for(int j = head[x] ; j ; j = e[j].n)
            if(dis[e[j].t] > dis[x] + e[j].w) {
                dis[e[j].t] = dis[x] + e[j].w;
                t.change(1 , 1 , n , e[j].t , dis[e[j].t]);
            }
        t.change(1 , 1 , n , x , LONG_LONG_MAX / 2);
    }
    for(int i = 1 ; i <= q ; ++ i)
        ANS[i] = min(dis[X[i]] + dis[Y[i]] , ANS[i]);
}
void graph() {
    memset(e , 0 , sizeof(e));
    memset(head , 0 , sizeof(head));
    tot = 0;
    for(int i = 1 ; i <= m ; ++ i) {
        addedge(U[i] , V[i] , W[i]);
        addedge(V[i] , U[i] , W[i]);
    }
    for(int i = 1 ; i <= n ; ++ i)
        if(vis[i])
            dijkstra(i);
}
void out() {
    for(int i = 1 ; i <= q ; ++ i)
        printf("%lld\n" , ANS[i]);
}
int main() {
    init();
    tree();
    graph();
    out();
    return 0;
}
//1. 建树,跑lca求最短路
//3. 原图上跑Dijkstra
Last modification:October 30th, 2018 at 09:51 pm

Leave a Comment