【题意】给你N个点，N条不同的边，Q次询问，求出u，v之间的最短路。
【分析】题意很简单，就是求最短路，但是Q次啊，暴力DIJ？当然不行，观察到这个题边的数目和点的数目是相同的，也就是说这个图是由一棵树加了一条边而形成的。而对于一棵树，如果有Q次询问最短路，那就可以用LCA来做，复杂度QlogN，但是现在加了一条边，可能会使有些点之间的路径变短。假设多加的这条边的两个端点是U，V，那么对于询问的X,Y，有这么三种情况，直接过LCA，或者经过U，V，详情见代码。
#include <bits/stdc++.h> #define met(a,b) memset(a,b,sizeof a) #define pb push_back #define mp make_pair #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lowbit(x) (x&(-x)) using namespace std; typedef long long ll; ll mod = 1e9+7; const int N=3e4+50; const int M=N*N+10; int n,m,k,root,son,dis[N],dep[N],fa[N][20],parent[N]; int d; vector<pair<int,int> >edg[N]; int Find(int x){ if(parent[x]!=x)parent[x]=Find(parent[x]); return parent[x]; } void Union(int x,int y){ x=Find(x); y=Find(y); if(x==y)return; parent[y]=x; } void dfs(int u,int f){ fa[u][0]=f; for(int i=1; i<20; i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int i=0; i<edg[u].size(); i++){ int v=edg[u][i].first; if(v==f)continue; dis[v]=dis[u]+edg[u][i].second; dep[v]=dep[u]+1; dfs(v,u); } } int Lca(int u,int v){ int U=u,V=v; if(dep[u]<dep[v])swap(u,v); for(int i=19; i>=0; i--){ if(dep[fa[u][i]]>=dep[v]){ u=fa[u][i]; } } if(u==v)return u; for(int i=19; i>=0; i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i]; v=fa[v][i]; } } return fa[u][0]; } int main(){ int u,v,w; int T; scanf("%d",&T); while(T--){ for(int i=0; i<N; i++)dis[i]=dep[i]=0,edg[i].clear(),parent[i]=i; met(fa,-1); scanf("%d%d",&n,&m); for(int i=1; i<=n; i++){ scanf("%d%d%d",&u,&v,&w); u++;v++; if(Find(u)==Find(v))root=u,son=v,d=w; else{ Union(u,v); edg[u].pb(mp(v,w)); edg[v].pb(mp(u,w)); } } dep[root]=1; dfs(root,-1); while(m--){ scanf("%d%d",&u,&v); u++;v++; int lca=Lca(u,v); int ans1=dis[u]+dis[v]-2*dis[lca]; int ans2=dis[u]+dis[son]-2*dis[Lca(u,son)]+dis[v]+dis[root]-2*dis[Lca(root,v)]+d; int ans3=dis[v]+dis[son]-2*dis[Lca(v,son)]+dis[u]+dis[root]-2*dis[Lca(root,u)]+d; printf("%d ",min(ans1,min(ans2,ans3))); } } return 0; }