HDU 2874 Connections between cities（LCA离线算法实现）

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

题意：

求两个城市之间的距离。

思路：

LCA题，注意原图可能不连通。

如果不了解离线算法的话，可以看我之前博客写的解释http://www.cnblogs.com/zyb993963526/p/7295894.html

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn=+;

 const int M=;

 int n, m, c;

 int etot,qtot;

 int ehead[maxn];

 int qhead[maxn];

 int mark[maxn];

 int dis[maxn];

 int vis[maxn];

 int ans[M];

 int p[maxn];

 struct node

 {

     int v,w;

     int next;

 }e[*maxn];

 struct Node

 {

     int v;

     int index;

     int next;

 }query[*M];

 void addEdge(int u, int v, int w)

 {

     e[etot].v=v;

     e[etot].w=w;

     e[etot].next=ehead[u];

     ehead[u]=etot++;

 }

 void addQuery(int u, int v, int i)

 {

     query[qtot].v=v;

     query[qtot].index=i;

     query[qtot].next=qhead[u];

     qhead[u]=qtot++;

 }

 int Find(int x)

 {

     return p[x]==x?x:p[x]=Find(p[x]);

 }

 void LCA(int u)

 {

     vis[u]=;

     for(int i=qhead[u];i!=-;i=query[i].next)

     {

         int v=query[i].v;

         if(vis[v] && !mark[Find(v)])  //mark数组是为了针对非连通图的情况

             ans[query[i].index]=dis[u]+dis[v]-*dis[Find(v)];

     }

     for(int i=ehead[u];i!=-;i=e[i].next)

     {

         int v=e[i].v;

         if(!vis[v])

         {

             dis[v]=dis[u]+e[i].w;

             LCA(v);

             p[v]=u;

         }

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d%d%d",&n,&m,&c))

     {

         etot=qtot=;

         memset(qhead,-,sizeof(qhead));

         memset(ehead,-,sizeof(ehead));

         for(int i=;i<=n;i++)  p[i]=i;

         while(m--)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             addEdge(u,v,w);

             addEdge(v,u,w);

         }

         for(int i=;i<=c;i++)

         {

             int u,v;

             scanf("%d%d",&u,&v);

             addQuery(u,v,i);

             addQuery(v,u,i);

         }

         memset(ans,-,sizeof(ans));

         memset(vis,,sizeof(vis));

         memset(mark,,sizeof(mark));

         for(int i=;i<=n;i++)

         {

             if(!vis[i])

             {

                 dis[i]=;

                 LCA(i);

                 mark[i]=;

             }

         }

         for(int i=;i<=c;i++)

         {

             if(ans[i]==-)   puts("Not connected");

             else printf("%d\n",ans[i]);

         }

     }

     return ;

 }