最短路

题目描述

给一个连通图，每次询问两点间最短路。每条边的长度都是1。

输入描述:

第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。
接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。
接下来一个整数q表示询问的个数（1≤ q≤ 100000）。
接下来q行每行两个整数a和b表示询问a和b之间的最短路。

输出描述:

每个询问输出一行表示答案。

题解

这道题我本来是不会的，通过阅读别人的题解才会，呜呜我好菜啊
这道题边的范围很好玩，。我们先假设恰好是即图为一棵树，那么我们可以通过最近公共祖先求得两点的最近距离为。现在又多出来100条边，这些多的边对于最短路有什么影响呢？如下图所示

即对于某个点作为中转点得到的路径长度会更小
那么我们对于剩下多出来的边跑单元最短路并记录下来，最后对于到的最小距离从和取一个min即可（i为中转点）。
我们来看一下具体实现方法

Part 1: 求解lca

对于此部分我附上一个我感觉还不错的讲解lca的视频（感觉视频对于初学者更友好）:https://www.bilibili.com/video/BV1N7411G7JD?from=search&seid=2296026282085823064
代码及注释

void dfs(int node,int fa){//node当前节点 fa表示他的父亲
    dep[node]=dep[fa]+1;//此数组存的是深度
    dp[node][0]=fa;//dp[i][j]表示节点i的2^j个父亲是谁
    for(int i=1;(1<<i)<=dep[node];++i){
        dp[node][i]=dp[dp[node][i-1]][i-1];//倍增思想
    }
    for(int i=head[node];~i;i=s[i].net){
        if(s[i].to==fa)continue;
        dfs(s[i].to,node);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int tep=dep[x]-dep[y];
    for(int j=0;tep;++j){
        if(tep&1)x=dp[x][j];
        tep>>=1;
    }//让两个点到同一深度
    if(x==y)return x;//如果一样就直接返回
    for(int j=21;j>=0&&x!=y;--j){
        if(dp[x][j]!=dp[y][j]){
            x=dp[x][j];
            y=dp[y][j];
        }
    }//找到不让两者父亲重合能够上跳的最大距离
    return dp[x][0];
}

Part 2 怎么找多余的那100条边

我们可以利用并查集，如果一条边的两个顶点已经一个父亲了，那么这时候这条边就是多余的了。我们可以把多余的边先记录下来并不添加到图上，等我们跑完dfs之后再添加到图上去跑最短路。

代码

#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define all(A) A.begin(), A.end()
#define fi first
#define se second
#define MP make_pair
#define rep(i,n) for(register int i=0;i<(n);++i)
#define repi(i,a,b) for(register int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(register int i=int(b);i>=(a);--i)
template<typename T>
inline T read(){
    T s=0,f=1; char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') f=-1;ch = getchar();}
    while(isdigit(ch)) {s=(s<<3)+(s<<1)+ch-48;ch = getchar();}
    return s*f;
}
#define gn() read<int>()
#define gl() read<ll>()
template<typename T>
inline void print(T x) {
    if(x<0) putchar('-'), x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
////////////////////////////////////////////////////////////////////////
const int N=1e5+100;
struct node{
    int now,to,net;
}s[2*N+100];
int f[N],dp[N][25],dep[N],dis[120][N],head[N];
int tot=0,num=0;
void add(int u,int v){
    s[++tot]={u,v,head[u]};
    head[u]=tot;
    s[++tot]={v,u,head[v]};
    head[v]=tot;
}
void dfs(int node,int fa){
    dep[node]=dep[fa]+1;
    dp[node][0]=fa;
    for(int i=1;(1<<i)<=dep[node];++i){
        dp[node][i]=dp[dp[node][i-1]][i-1];
    }
    for(int i=head[node];~i;i=s[i].net){
        if(s[i].to==fa)continue;
        dfs(s[i].to,node);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    int tep=dep[x]-dep[y];
    for(int j=0;tep;++j){
        if(tep&1)x=dp[x][j];
        tep>>=1;
    }
    if(x==y)return x;
    for(int j=21;j>=0&&x!=y;--j){
        if(dp[x][j]!=dp[y][j]){
            x=dp[x][j];
            y=dp[y][j];
        }
    }
    return dp[x][0];
}
void bfs(int node){
    num++;
    dis[num][node]=0;
    queue<int> Q;
    Q.push(node);
    while(!Q.empty()){
        int star=Q.front();Q.pop();
        for(int i=head[star];~i;i=s[i].net){
            if(dis[num][s[i].to]>dis[num][star]+1){
                dis[num][s[i].to]=dis[num][star]+1;
                Q.push(s[i].to);
            }
        }
    }
}
int found(int x){
    if(f[x]==x)return x;
    return f[x]=found(f[x]);
}
vector<pii> V;
////////////////////////////////////////////////////////////////////////
int main(){
    int n=gn(),m=gn();
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;++i){
        head[i]=-1;
        f[i]=i;
    }
    for(int i=0;i<m;++i){
        int u=gn(),v=gn();
        if(found(u)==found(v))V.pb({u,v});
        else {
            f[found(u)]=found(v);
            add(u,v);
        }
    }
    dfs(1,0);
    for(auto k:V){
        add(k.fi,k.se);
    }
    for(auto k:V){
        bfs(k.fi);
    }
    int q=gn();
    while(q--){
        int a=gn(),b=gn();
        int ans=dep[a]+dep[b]-2*dep[lca(a,b)];
        for(int i=1;i<=num;++i){
            ans=min(ans,dis[i][a]+dis[i][b]);
        }
        printf("%d\n",ans);
    }
}
/**
* In every life we have some trouble
* When you worry you make it double
* Don't worry,be happy.
**/