给了你n个村庄把,然后m条路径,q个询问,问你两个点之间的最短距离
分析:由于按照题意来说本图是没有环的,所以求a,b的最近公共祖先 到他们的各自的距离之和就是 那个他们的最短路啦,用的是tarjan来做的,我的方法定义了一个dis数组来随时记录路径的长度,其它大神各有自己的神奇之法
#include<iostream> #include<cstdio> #include<list> #include<algorithm> #include<cstring> #include<string> #include<queue> #include<stack> #include<map> #include<vector> #include<cmath> #include<memory.h> #include<set> #include<cctype> #define ll long long #define LL __int64 #define eps 1e-8 #define inf 0xfffffff //const ll INF = 1ll<<61; using namespace std; //vector<pair<int,int> > G; //typedef pair<int,int > P; //vector<pair<int,int> > ::iterator iter; // //map<ll,int >mp; //map<ll,int >::iterator p; const int N = 10000 + 5; const int MAXN = 2000000 + 5; int pre[N]; int head[N],qhead[N]; int dis[N]; bool vis[N]; int tot,qtot; typedef struct Node { int from,nex,to; int lca; }; Node edge[N * 2],qedge[MAXN]; void clear() { memset(dis,0,sizeof(dis)); memset(vis,false,sizeof(vis)); memset(head,-1,sizeof(head)); memset(qhead,-1,sizeof(qhead)); for(int i=0;i<=N;i++) pre[i] = i; tot = qtot = 0; } void addedge(int u,int v,int w) { edge[tot].nex = head[u]; edge[tot].to = v; edge[tot].lca = w; head[u] = tot++; } void addqedge(int u,int v) { qedge[qtot].nex = qhead[u]; qedge[qtot].from = u; qedge[qtot].to = v; qedge[qtot].lca = -1; qhead[u] = qtot++; } int find(int x) { if(pre[x] != x)return find(pre[x]); return pre[x]; } void LCA(int u) { pre[u] = u; vis[u] = true; for(int i=head[u];i!=-1;i=edge[i].nex) { if(!vis[edge[i].to]) { dis[edge[i].to] = dis[u] + edge[i].lca; LCA(edge[i].to); pre[edge[i].to] = u; } } for(int i=qhead[u];i!=-1;i=qedge[i].nex) { if(vis[qedge[i].to]) { qedge[i].lca = dis[qedge[i].to] - dis[find(qedge[i].to)] + dis[u] - dis[find(qedge[i].to)]; qedge[i ^ 1].lca = qedge[i].lca; } } } int main() { int n,m,q; while(scanf("%d %d %d",&n,&m,&q) == 3) { clear(); while(m--) { int u,v,w; scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } for(int i=0;i<q;i++) { int u,v; scanf("%d %d",&u,&v); addqedge(u,v); addqedge(v,u); } for(int i=1;i<=n;i++) if(!vis[i]) LCA(i); for(int i=0;i<qtot;i += 2) { int u = qedge[i].from; int v = qedge[i].to; if(find(u) != find(v)) puts("Not connected"); else printf("%d\n",qedge[i].lca); } } return 0; }
HDU2874 Connections between cities 最近公共祖先+离线,布布扣,bubuko.com
HDU2874 Connections between cities 最近公共祖先+离线
原文:http://blog.csdn.net/yitiaodacaidog/article/details/25560613