最短路

题意： 给定一个个点条边的无向连通图，所有边边权均为，次询问，每次询问图中两点的最短路径，保证无自环与重边。
数据范围：

题解：
由于是无向连通图，一眼看上去是一个不可做题。
卡了很久很久才发现了数据范围有点不寻常，考虑最多有条多余的边，其余边可以组成一棵树。
那么如果是一棵树则可以先预处理后用，本题相较于树多了一些边，这些边可能会使得由树得到的树上两点唯一路径变得不再唯一，那么就可能会使得树上两点的路径变得更短。
那么考虑何时会导致这些边有效果：
对于一条边，如果树上两点距离大于，则途径这条路的所有路径都会被更新。
那么只需要用多余的边依次对树上的路径进行更新即可，即加上这条边对图进行一次最短路求解即可，由于边权为，可以直接用。

解释：考虑多出来的边，以及本次询问的两个点，则求

本题卡常严重，所以尽可能的优化能优化的部分。

代码：

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

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();} 
    return x * f;
}

const int N = 1e5 + 200;
const int M = N << 1;
const int Mdep = 20;
int h[N], e[M], ne[M], idx;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int dep[N];
int f[N][Mdep + 1];
void dfs(int u, int fa) {
    f[u][0] = fa;
    dep[u] = dep[fa] + 1;
    for(int i = 1; (1 << i) <= dep[u]; ++i) 
        f[u][i] = f[f[u][i - 1]][i - 1];

    for(int i = h[u]; i != -1; i = ne[i]) 
        if(e[i] != fa) dfs(e[i], u);
}

int LCA(int a, int b) {
    if(dep[a] < dep[b]) swap(a, b);
    for(int k = Mdep; k >= 0; k--) 
        if(dep[f[a][k]] >= dep[b]) a = f[a][k];
    if(a == b) return a;
    for(int k = Mdep; k >= 0; k--)
        if(f[a][k] != f[b][k]) a = f[a][k], b = f[b][k];
    return f[a][0];
}

int dist(int a, int b) {
    return dep[a] + dep[b] - 2 * dep[LCA(a, b)];
}

int p[N];
int find(int x) {
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

int dis[110][N];
int q[N];
int cnt;
void bfs(int fir) {
    ++cnt;
    dis[cnt][fir] = 0;
    int hh = 0, tt = -1;
    q[++tt] = fir;
    while(hh <= tt) {
        int u = q[hh++];
        for(int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if(dis[cnt][v] > dis[cnt][u] + 1) {
                dis[cnt][v] = dis[cnt][u] + 1;
                q[++tt] = v;
            }
        }
    }
}

struct Node{
    int x, y;
};
vector<Node> sur;

int main()
{
    int n = read(), m = read();
    idx = 0;
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= n; i++) h[i] = -1, p[i] = i;

    for(int i = 1; i <= m; i++) {
        int a = read(), b = read();
        int pa = find(a), pb = find(b);
        if(pa == pb) sur.push_back({a, b});
        else {
            p[pa] = pb;
            add(a, b);
            add(b, a);
        }
    }

    dfs(1, 0);

    for(auto &t : sur) {
        add(t.x, t.y);
        add(t.y, t.x); 
    }

    for(auto &t : sur) bfs(t.x);

    int Q = read();
    while(Q--) {
        int a = read(), b = read();
        int res = dist(a, b);
        for(int i = 1; i <= cnt; i++) 
            res = min(res, dis[i][a] + dis[i][b]);
        printf("%d\n", res);
    }
    return 0;
}