CF E51 F. The Shortest Statement//lca(倍增)+dijkstra+dsu ※

https://codeforc.es/contest/1051/problem/F

題意：

給一個聯通simply圖，n(1e5)個點，m條邊，m-n<=20，給q(1e5)個詢問，每個詢問給ui和vi，求ui和vi之間的最短路。

思路：

發現邊少，那麼我們在它的樹形圖上思考（并查集處理出來任意樹形圖，不考慮多的m-n+1條邊），那麼任意兩點距離就是dis[u]+dis[v]-2*dis[lca(u,v)]。

那麼多了這m-n+1條邊，相當多最了多了42個點，那麼枚舉給的詢問經過這些點能否得到更小的答案。

那麼對這42個點跑一邊最短路。ans=max(樹上的最短路，經過多出來的邊連接配接的點的最短路)。

結論：處理出來x 的單源最短路可得到所有經過x的最短路。

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define FI first
#define SE second
#define MP make_pair
#define PII pair<int,int>
const LL mod = 1e9+7;
const int MX = 1e5+5;
struct no{LL w,v;};
bool operator<(const no &x,const no &y){return x.w>y.w;}
int fa[MX];int found(int x){if(fa[x]==x)return x;return fa[x]=found(fa[x]);}
int n,m;
vector<no>g[MX],T[MX];
vector<int>v;map<int,int>id;
LL di[50][MX],bei[MX][22],de[MX],dis[MX];

void dij(int s){
    for(int i=1;i<=n;i++) di[id[s]][i]=LLONG_MAX/2;
    priority_queue<no>pq;
    pq.push(no{0,s});di[id[s]][s]=0;
    while(!pq.empty()){
        int now=pq.top().v;pq.pop();
        for(no i:g[now]){
            LL zz=di[id[s]][now]+i.w;
            if(zz<di[id[s]][i.v]) di[id[s]][i.v]=zz,pq.push(no{zz,i.v});
        }
    }
}
void dfs(int v,int p){//所有都是向上走2^k步 所代表的含義
    for(auto i:T[v]) {
        if(i.v!=p){
            de[i.v]=de[v]+1;bei[i.v][0]=v;dis[i.v]=dis[v]+i.w;
            dfs(i.v,v);
        }
    }
}
void initLCA(int nn){
    bei[1][0]=-1;dfs(1,-1);
    for(int k=0;k<=20;k++){
        for(int v=1;v<=nn;v++){
            if(bei[v][k]<0)bei[v][k+1]=-1;
            else bei[v][k+1]=bei[bei[v][k]][k];
        }
    }
}
int getLCA(int u,int v){
    if(de[u]>de[v]) swap(u,v);
    for(int k=0;k<22;k++){
        if((de[v]-de[u])>>k&1) v=bei[v][k];
    }
    if(u==v) return u;
    for(int k=21;k>=0;k--){
        if(bei[u][k]!=bei[v][k]){u=bei[u][k],v=bei[v][k];}
    }
    return bei[u][0];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int ui,vi,di;scanf("%d%d%d",&ui,&vi,&di);
        int fx=found(ui),fy=found(vi);
        if(fx==fy) v.push_back(ui),v.push_back(vi);
        else T[ui].push_back(no{di,vi}),T[vi].push_back({di,ui}),fa[fx]=fa[fy];
        g[ui].push_back(no{di,vi}),g[vi].push_back({di,ui});
    }
    sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=0;i<(int)v.size();i++)id[v[i]]=i;
    for(auto i:v)dij(i);
    initLCA(n);
    int Q;cin>>Q;while(Q--){
        int ui,vi;scanf("%d%d",&ui,&vi);
        int lca=getLCA(ui,vi);
        LL ans=dis[ui]+dis[vi]-2*dis[lca];
        for(int i=0;i<(int)v.size();i++){
            ans=min(ans,di[i][ui]+di[i][vi]);
        }
        printf("%I64d\n",ans);
    }
    return 0;
}