图不一定联通,所以用并查集找各个联通块的祖先分别建图,之后就和LCA的步骤差不多了
#include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<algorithm> #include<vector> using namespace std; inline int read(){ int sum=0,x=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') x=0; ch=getchar(); } while(ch>='0'&&ch<='9') sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar(); return x?sum:-sum;; } inline void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } const int M=1e4+4; const int maxlog=14; struct node{ int v,nextt,w; }e[M<<2]; int head[M],deep[M],grand[M][maxlog],dis[M][maxlog],f[M],s,n,tot,root,sign; void addedge(int u,int v,int w){ e[tot].v=v; e[tot].w=w; e[tot].nextt=head[u]; head[u]=tot++; } int find(int x){ return x==f[x]?x:f[x]=find(f[x]); } void dfs(int x){ for(int i=1;i<=s;i++){ grand[x][i]=grand[grand[x][i-1]][i-1]; dis[x][i]=dis[x][i-1]+dis[grand[x][i-1]][i-1]; if(!grand[x][i]) break; } for(int i=head[x];~i;i=e[i].nextt){ int v=e[i].v; // cout<<"exit"<<endl; if(v!=grand[x][0]){ grand[v][0]=x; deep[v]=deep[x]+1; dis[v][0]=e[i].w; dfs(v); } } } void init(){ s=floor(log(n+0.0)/log(2.0)); deep[0]=-1; dfs(root); } int LCA(int a,int b){ if(deep[a]>deep[b]) swap(a,b); int ans=0; for(int i=s;i>=0;i--) if(deep[a]<deep[b]&&deep[a]<=deep[grand[b][i]]) ans+=dis[b][i],b=grand[b][i]; for(int i=s;i>=0;i--) if(grand[a][i]!=grand[b][i]) ans+=dis[a][i],a=grand[a][i],ans+=dis[b][i],b=grand[b][i]; if(a!=b) ans+=dis[a][0],ans+=dis[b][0]; return ans; } int main(){ int m,k; while(~scanf("%d%d%d",&n,&m,&k)){ for(int i=0;i<=n;i++) f[i]=i,head[i]=-1,deep[i]=0; memset(grand,0,sizeof(grand)); memset(dis,0,sizeof(dis)); tot=0; while(m--){ int x=read(),y=read(),w=read(); addedge(x,y,w); addedge(y,x,w); int p=find(x); int q=find(y); if(p!=q) f[q]=p; } for(int i=1;i<=n;i++){ if(f[i]==i){ root=i; init(); } // cout<<"!!!"<<f[i]<<endl; } /* for(int i=1;i<=n;i++) cout<<deep[i]<<" "; cout<<endl;*/ while(k--){ int u=read(),v=read(); int x=find(u); int y=find(v); if(x==y){ write(LCA(u,v)); putchar('\n'); } else puts("Not connected"); } } return 0; }