给n顶点和m条边求任意两点的最短距离，只要找到他们的最近公共祖先就可以求出他们的最短距离，先处理后询问，只是很明显的离线LCA可以用tarjan离线算法。
昨天做了一道类似的，此题和poj1330很接近，几乎是它的一个扩展。如果做个那题此题可迎刃而解。
#include<iostream> #include<vector> using namespace std; const int N=10009; int father[N],anc[N],vis[N],r[N],dis[N],color[N]; struct node { int v,w; }; vector<node> point[N],Q[N]; int ans[1000009]; int n,q; int count; int find(int x) { int i,t; for(i=x;father[i]>0;i=father[i]); while(i!=x)//把所有子节点都指向根， { t=father[x]; father[x]=i; x=t; } return i; } void Union(int a,int b) { int x=find(a); int y=find(b); if(x!=y) { if(r[x]<r[y])//安秩合并 { father[x]=y; r[y]+=r[x]; } else { father[y]=x; r[x]+=r[y]; } } } void tarjan_lca(int u,int d) { anc[u]=u; vis[u]=1; int i; dis[u]=d; for(i=0;i<point[u].size();i++) { int v=point[u][i].v; if(!vis[v]) { tarjan_lca(v,dis[u]+point[u][i].w); Union(u,v); anc[find(u)]=u; } } color[u]=count; for(i=0;i<Q[u].size();i++)//查询 { int v=Q[u][i].v; if(color[v]) { if(color[v]==count)//判断是否属于同一集合 { ans[Q[u][i].w]=dis[u]+dis[v]-2*dis[anc[find(v)]]; } else ans[Q[u][i].w]=-1; } } } void init() { for(int i=0;i<=n;i++) { father[i]=-1; vis[i]=0; anc[i]=0; r[i]=1; color[i]=0; point[i].clear(); Q[i].clear(); } memset(ans,-1,sizeof(ans)); } int main() { int m,a,b,i,w; while(scanf("%d%d%d",&n,&m,&q)!=EOF) { init(); for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&w); node temp; temp.w=w; temp.v=b; point[a].push_back(temp); temp.v=a; point[b].push_back(temp); } for(i=0;i<q;i++) { scanf("%d%d",&a,&b); node temp; temp.v=b; temp.w=i; Q[a].push_back(temp); temp.v=a; Q[b].push_back(temp); } count=1; for(i=1;i<=n;i++) { if(!vis[i]) { tarjan_lca(i,0); count++; } } for(i=0;i<q;i++) { if(ans[i]==-1) printf("Not connected "); else printf("%d ",ans[i]); } } return 0; }
我其实对STL的容器不是很了解，所以刚开始准备用结构体数组，可是数组太多，怕超。所以用了vector容器，也好顺便学习一下容器