每日一题 7月7日 最短路 01最短路+树的LCA

题目链接：https://ac.nowcoder.com/acm/problem/19814
题目大意：

思路：
m最大为n+100，并且连通。我们可以假设开始一棵树。有q个查询u-v的最短路。然后添加了100条边。那么最短路可以发生变化的一定经过了这些边。假设这些边为x-y。那么经过了x点。我们以x为起点跑一个最短路，那么a-b的最短路可能为ans[i]=min(ans[i], dis[a]+dis[b])。当然对于每个查询我们不能去枚举一次100条边。而是用100条边上的点跑完最短路都去更新下q个查询。复杂度O(100qlogn)

#include <bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    int x;
    int y;
    int i;
}ans[1000050];
vector<node> G[1000050];
int vis[1000050], visE[1000050], ds[1000050], pw[1000050]={1};
struct LCA{
    int d[1000050], fa[1000050][22], lg[1000050];
    void init(int n, int root){//预处理
        for(int i = 1; i <= n; ++i){
            lg[i] = lg[i-1] + (1 << lg[i-1] == i);
        }
        dfs(root, 0);
    }
    void dfs(int now, int father){
        vis[now]=1;
        ds[now]=ds[father]+1;
        fa[now][0]=father; d[now]=d[father]+1;
        for(int i=1; i<=lg[d[now]]; ++i){
            fa[now][i]=fa[fa[now][i-1]][i-1];
        }
        for(auto x: G[now]){
            if(x.x!=father&&!vis[x.x]){
                visE[x.i]=1;
                dfs(x.x, now);
            }
        }
    }
    int lca(int x, int y){//LCA
        if(d[x]<d[y]) swap(x, y);
        while(d[x]>d[y]){
            x=fa[x][lg[d[x]-d[y]]-1];
        }
        if(x==y) return x;
        for(int k=lg[d[x]]-1; k>=0; --k){
            if(fa[x][k]!=fa[y][k]){
                x=fa[x][k], y=fa[y][k];
            }
        }
        return fa[x][0];
    }

}lca;

queue<int> q;
int dis[1000050];
void bfs(int u, int Q){
    memset(dis, -1, sizeof(dis));
    q.push(u), dis[u]=0;
    while(!q.empty()){//跑一次最短路
        int to=q.front(); q.pop();
        for(auto x: G[to]){
            if(dis[x.x]==-1){
                dis[x.x]=dis[to]+1;
                q.push(x.x);
            }
        }
    }
    for(int i=1; i<=Q; i++){//更新每个查询
        ans[i].i=min(ans[i].i, dis[ans[i].x]+dis[ans[i].y]);
    }
}

int form[1000050], to[1000050];
int main(){

    for(int i=1; i<=30; i++){
        pw[i]=pw[i-1]*2;
    }
    int n, m, x, y; scanf("%d%d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d%d", &x, &y);
        form[i]=x, to[i]=y;
        G[x].push_back(node{y,0, i});
        G[y].push_back(node{x,0, i});
    }
    lca.init(n+3, 1);//从图中得到一颗树
    int q; scanf("%d", &q);
    for(int i=1; i<=q; i++){
        scanf("%d%d", &x, &y);
        ans[i]=node{x, y, ds[x]+ds[y]-2*ds[lca.lca(x, y)]};
    }
    for(int i=1; i<=m; i++){
        if(!visE[i]){//非树边
            bfs(form[i], q);
        }
    }
    for(int i=1; i<=q; i++){
        printf("%d\n", ans[i].i);
    }

    return 0;
}