自己做网站背景图片,php网页模板,单位建网站的详细步骤,做er图的网站http://acm.hdu.edu.cn/showproblem.php?pid2874 题意#xff1a; 求两个城市之间的距离。 思路#xff1a; LCA题#xff0c;注意原图可能不连通。 如果不了解离线算法的话#xff0c;可以看我之前博客写的解释http://www.cnblogs.com/zyb993963526/p/7295894.html 1 #in…http://acm.hdu.edu.cn/showproblem.php?pid2874 题意 求两个城市之间的距离。 思路 LCA题注意原图可能不连通。 如果不了解离线算法的话可以看我之前博客写的解释http://www.cnblogs.com/zyb993963526/p/7295894.html 1 #includeiostream2 #includealgorithm3 #includecstring4 #includecstdio5 #includesstream6 #includevector7 #includestack8 #includequeue9 #includecmath10 #includemap11 #includeset12 using namespace std;13 typedef long long ll;14 typedef pairint,int pll;15 const int INF 0x3f3f3f3f;16 const int maxn100005;17 const int M1000010;18 19 int n, m, c;20 int etot,qtot;21 int ehead[maxn];22 int qhead[maxn];23 int mark[maxn];24 int dis[maxn];25 int vis[maxn];26 27 int ans[M];28 int p[maxn];29 30 struct node31 {32 int v,w;33 int next;34 }e[2*maxn];35 36 struct Node37 {38 int v;39 int index;40 int next;41 }query[2*M];42 43 void addEdge(int u, int v, int w)44 {45 e[etot].vv;46 e[etot].ww;47 e[etot].nextehead[u];48 ehead[u]etot;49 }50 51 void addQuery(int u, int v, int i)52 {53 query[qtot].vv;54 query[qtot].indexi;55 query[qtot].nextqhead[u];56 qhead[u]qtot;57 }58 59 int Find(int x)60 {61 return p[x]x?x:p[x]Find(p[x]);62 }63 64 void LCA(int u)65 {66 vis[u]1;67 for(int iqhead[u];i!-1;iquery[i].next)68 {69 int vquery[i].v;70 if(vis[v] !mark[Find(v)]) //mark数组是为了针对非连通图的情况71 ans[query[i].index]dis[u]dis[v]-2*dis[Find(v)];72 }73 74 for(int iehead[u];i!-1;ie[i].next)75 {76 int ve[i].v;77 if(!vis[v])78 {79 dis[v]dis[u]e[i].w;80 LCA(v);81 p[v]u;82 }83 }84 }85 86 int main()87 {88 //freopen(in.txt,r,stdin);89 while(~scanf(%d%d%d,n,m,c))90 {91 etotqtot0;92 memset(qhead,-1,sizeof(qhead));93 memset(ehead,-1,sizeof(ehead));94 for(int i1;in;i) p[i]i;95 96 while(m--)97 {98 int u,v,w;99 scanf(%d%d%d,u,v,w);
100 addEdge(u,v,w);
101 addEdge(v,u,w);
102 }
103
104 for(int i1;ic;i)
105 {
106 int u,v;
107 scanf(%d%d,u,v);
108 addQuery(u,v,i);
109 addQuery(v,u,i);
110 }
111
112 memset(ans,-1,sizeof(ans));
113 memset(vis,0,sizeof(vis));
114 memset(mark,0,sizeof(mark));
115 for(int i1;in;i)
116 {
117 if(!vis[i])
118 {
119 dis[i]0;
120 LCA(i);
121 mark[i]1;
122 }
123 }
124 for(int i1;ic;i)
125 {
126 if(ans[i]-1) puts(Not connected);
127 else printf(%d\n,ans[i]);
128 }
129 }
130 return 0;
131 } 转载于:https://www.cnblogs.com/zyb993963526/p/7295969.html
