http://acm.hdu.edu.cn/showproblem.php?pid=2874

題解：LCA

參考文章：?https://blog.csdn.net/weixin_43272781/article/details/88797088

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int #define endl "\n" using namespace std; typedef long long ll; //typedef __int128 lll; const int N=100000+10; const int M=100000+10; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,p,l,r,u,v,c; int ans,cnt,flag,temp,sum,num; int pre[N]; bool vis[N]; int dep[N]; int dp[N][21]; int dist[N]; int que[N]; int first[N]; char str; struct node{int v,w; }x; struct query{int e,id; }y; vector<node>G[N]; int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);} void marge(int u,int v){int tu=find(u);int tv=find(v);if(tu!=tv){pre[tv]=tu;} } void dfs(int u,int deep){vis[u]=1;que[++num]=u;//num在此處相當于dfs_clockfirst[u]=num;//表示第一次走的編號dep[num]=deep;for(int i=0,j=G[u].size();i<j;i++){int v=G[u][i].v;int w=G[u][i].w;if(!vis[v]){dist[v]=dist[u]+w;dfs(v,deep+1);que[++num]=u;dep[num]=deep;}} } void ST(int n){for(int i=1;i<=n;i++){dp[i][0]=i;}for(int i=0;(1<<i)<n;i++){for(int j=1;j+(1<<i)<n;j++){int a=dp[j][i],b=dp[j+(1<<i)][i];dp[j][i+1]=dep[a]<dep[b]?a:b;}} } int RMQ(int l,int r){k=log2(r-l+1);int a=dp[l][k],b=dp[r-(1<<k)+1][k];return dep[a]<dep[b]?a:b; } int LCA(int u,int v){int x = first[u] , y = first[v];if(x > y) swap(x,y);int res = RMQ(x,y);return que[res]; } void init(){for(int i=1;i<=n;i++){G[i].clear();pre[i]=i;}memset(vis,0,sizeof(vis));memset(dep,0,sizeof(dep));memset(dist,0,sizeof(dist));memset(dp,0,sizeof(dp));memset(que,0,sizeof(que));cnt=0,num=0; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endif//ios::sync_with_stdio(false);//cin.tie(0);//cout.tie(0);//scanf("%d",&t);while(~scanf("%d%d%d",&n,&m,&c)){init();for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&k);x.v=v;x.w=k;G[u].push_back(x);x.v=u;G[v].push_back(x);marge(u,v);}for(int i=1;i<=n;i++){if(pre[i]==i){dist[i]=0;dfs(i,1);}}ST(2*n-1);for(int i=1;i<=c;i++){scanf("%d%d",&u,&v);if(find(u)==find(v)){int lca=LCA(u,v);cout<<dist[u]+dist[v]-2*dist[lca]<<endl;}else{cout<<"Not connected"<<endl;}}}#ifdef DEBUGprintf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC); #endif//cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的Connections between cities的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。