最短路

题意

给一个连通图，每次询问两点间最短路。

分析

首先我们取联通的条边，利用，处理出询问的答案。

然后我们最多还剩下条边，我们对这些边的点跑，处理出所有点到该点的距离，
然后遍历所有的询问，更新答案。

时间有点紧

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 201110;
const int M = 1e9+7;
int n,m,q,t=20;

int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
    return f*x;
}

void print(int x)
{
    if(x < 0) {putchar('-');x = -x;}
    if(x/10) print(x/10);
    putchar(x%10+'0');
}

int head[maxn],to[maxn],Next[maxn],cnt = 2;

void add(int u,int v)
{
    to[cnt] = v;Next[cnt] = head[u];head[u] = cnt;cnt++;
}

int d[maxn],fa[maxn][25];

void dfs(int u,int pre)
{   
    d[u] = d[pre]+1;
    fa[u][0] = pre;
    for(int i = 1; (1<<i) <= d[u]; i++)
    {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int i = head[u]; i ; i = Next[i])
    {
        int v = to[i];
        if(v == pre) continue;
        dfs(v,u);
    }
}

int lca(int x,int y)
{
    if(d[x] > d[y]) swap(x,y);
    for(int i = t; i >= 0; i--)
    {
        if(d[fa[y][i]] >= d[x])
        {
            y = fa[y][i];
        }
    }
    if(x == y) return x;
    for(int i = t; i >= 0; i--)
    {
        if(fa[y][i] != fa[x][i])
        {
            y = fa[y][i];x = fa[x][i];
        }
    }
    return fa[x][0];
}

int dist(int x,int y)
{
    return d[x]+d[y]-2*d[lca(x,y)];
}

struct node
{
    int x,y;
}a[maxn];

int ans[maxn],pre[maxn];

vector<pii> vt;

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

int dis[maxn];
bool vis[maxn];

int que[maxn];

void spfa(int u)
{
    for(int i = 1; i <= n; i++) 
    {
        vis[i] = 0;
    }
    int h = 1,r = 1;
    dis[u] = 0;que[1] = u;vis[u] = 1;
    while(h <= r)
    {
        u = que[h++];
        for(int i = head[u]; i ; i = Next[i])
        {
            int v = to[i];
            if(vis[v]) continue;
            dis[v] = dis[u]+1;
            vis[v] = 1;
            que[++r] = v;
        }
    }
    for(int i = 1; i <= q; i++) 
    {
        ans[i] = min(ans[i],dis[a[i].x]+dis[a[i].y]);
    }
}

map<int,bool> mp;

signed main()
{
    n = read(),m = read();
    for(int i = 1; i <= n; i++) 
    {
        pre[i] = i;
    }
    for(int i = 1,u,v; i <= m; i++) 
    {
        u = read(),v = read();
        if(find(u) == find(v))
        {
            vt.push_back({u,v});
            continue;
        }
        add(u,v);
        add(v,u);
        pre[find(u)] = find(v);
    }
    dfs(1,0);
    for(auto i : vt)
    {   
        add(i.first,i.second);
        add(i.second,i.first);
    }
    q = read();
    for(int i = 1; i <= q; i++) 
    {
        a[i].x = read(),a[i].y = read();
        ans[i] = dist(a[i].x,a[i].y);
    }
    for(auto i : vt)
    {
        if(!mp[i.first])
        {
            mp[i.first] = 1;
            spfa(i.first);
        }
        if(!mp[i.second])
        {
            mp[i.second] = 1;
            spfa(i.second);
        }
    }
    for(int i = 1; i <= n; i++) 
    {
        print(ans[i]);
        putchar('\n');
    }
    return 0;
}