题目链接：点此跳转
题目大意：给一个连通图，每次询问两点间最短路。每条边的长度都是1。
第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。
解题思路：
因为这道题边的范围比较特别，1≤m≤n+100。我们先假设m恰好是n-1即图为一棵树，那么我们可以通过最近公共祖先求得两点的最近距离为dep[a]+dep[b]-2*dep[lca(a,b)]。现在又多出来100条边，我们要怎么处理呢？ 答案是：bfs 直接对这些边的一个端点开始暴力搜索最短路即可。
Code：
#include<iostream> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int> pii; const int N=1e5+5; int dp[N][25],f[N],dep[N],dis[120][N],head[N]; int tot,num; vector<pii> ve; struct node{ int now,to,net; }s[N*2+100]; void add(int u,int v){ //链式前向星存图 s[++tot]={u,v,head[u]}; head[u]=tot; s[++tot]={v,u,head[v]}; head[v]=tot; } int find(int x){ //最小生成树 if(f[x]==x) return x; return f[x]=find(f[x]); } 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 main(){ int n,m; scanf("%d%d",&n,&m); memset(dis,0x3f3f,sizeof dis); for(int i=1;i<=n;i++){ head[i]=-1; f[i]=i; } for(int i=0;i<m;i++){ int u,v; scanf("%d%d",&u,&v); if(find(u)==find(v)) ve.push_back({u,v}); else{ f[find(u)]=find(v); add(u,v); } } dfs(1,0); // lca 预处理 for(auto k:ve){ add(k.first,k.second); } for(auto k:ve){ //求这个点到其他点的最短距离 bfs(k.first); } int q; scanf("%d",&q); while(q--){ int a,b; scanf("%d%d",&a,&b); 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); } return 0; }