題目鏈接：點擊查看

題目大意：給出n個點代表城市，再給出m條邊將其連接，每條邊都有邊權，題目保證給出的圖無環，現在給出兩個點，首先詢問兩個點是否互相連通，若可以連通，詢問兩點之間的距離

題目分析：判斷連通我們直接用并查集維護分塊就好了，因為是無向圖，所以最后對于每個分塊隨便選一個點當做根節點跑一遍dfs維護一下樹上前綴和，最后就可以直接判斷了，算是一個模板題吧，比較簡單

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e4+100;unordered_map<string,int>mp;int n,m,q,limit;int fa[N];bool vis[N];struct Node {int to,w;Node(int TO,int W){to=TO;w=W;} };vector<Node>node[N];int du[N];int deep[N],dp[N][20];LL sum[N];void dfs(int u,int f,int dep) {deep[u]=dep;dp[u][0]=f;for(int i=1;i<=limit;i++)dp[u][i]=dp[dp[u][i-1]][i-1];for(int i=0;i<node[u].size();i++){int v=node[u][i].to;int w=node[u][i].w;if(v==f)continue;sum[v]=sum[u]+w;dfs(v,u,dep+1);} }int LCA(int x,int y) {if(deep[x]<deep[y])swap(x,y);for(int i=limit;i>=0;i--)if(deep[x]-deep[y]>=(1<<i))x=dp[x][i];if(x==y)return x;for(int i=limit;i>=0;i--)if(dp[x][i]!=dp[y][i]){x=dp[x][i];y=dp[y][i];}return dp[x][0]; }int find(int x) {return x==fa[x]?x:fa[x]=find(fa[x]); }void merge(int x,int y) {int xx=find(x);int yy=find(y);if(xx!=yy)fa[xx]=yy; }void init() {memset(du,0,sizeof(du));for(int i=1;i<=n;i++){node[i].clear();fa[i]=i;vis[i]=false;sum[i]=0;}limit=log2(n)+1; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);while(scanf("%d%d%d",&n,&m,&q)!=EOF){init();while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);node[u].push_back(Node(v,w));node[v].push_back(Node(u,w));merge(u,v);}for(int i=1;i<=n;i++){int pos=find(i);if(vis[pos])continue;vis[pos]=true;dfs(pos,0,0);}while(q--){int a,b;scanf("%d%d",&a,&b);int aa=find(a);int bb=find(b);if(aa!=bb)printf("Not connected\n");else{int lca=LCA(a,b);printf("%lld\n",sum[a]+sum[b]-2*sum[lca]);}}}return 0; }

?

總結

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

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