题目意思是给你n个顶点m条边，再给你每条边的权，和一个方向，那个输入可以参照poj1984，那个方向是没有用的，再下面有K个询问，求两点间的最短距离。
我用了两种方法写此题，一种是RMQ+LCA模板
#include<iostream> #include<vector> #include<cmath> #include<algorithm> using namespace std; const int N=60008; int dis[N],vis[N],val[N],p[N]; int first[N*2],node[N*2],dep[N*2],dp[N*2][25]; int mi[25];//移位运算 struct Node { int v,w; }; vector<Node>map[N];//邻接表 void dfs(int &index,int u,int d,int dd) { index++;//时间搓,全部遍历一次并记录所有节点的父亲，为查找公共祖先做准备 node[index]=u; dep[index]=d; vis[u]=1; first[u]=index; for(int i=0;i<map[u].size();i++) { int v=map[u][i].v; if(!vis[v]) { dis[v]=dd+map[u][i].w; dfs(index,v,d+1,dis[v]); index++; node[index]=u; dep[index]=d; } } } void rmq_init(int n)//RMQ预处理 { int i; int K = (int)(log((double)n) / log(2.0)); for(i=1; i<=n; i++) dp[i][0] = i; for(int j=1; j<=K; j++) for(i=1; i+mi[j]-1 <= n ; i++) { int a = dp[i][j-1]; int b = dp[i+mi[j-1]][j-1]; if(dep[a] < dep[b]) dp[i][j] = a; else dp[i][j] = b; } } int rmq(int x,int y) { int k=(int)(log((double)(y-x+1))/log(2.0)); int a=dp[x][k]; int b=dp[y-mi[k]+1][k]; if(dep[a]<dep[b])//最近公共祖先的深度 return a; else return b; } int lca(int a,int b) { int x=first[a]; int y=first[b]; int k; if(x>y)//可用swap，但是我以前用了超时，所以再也不敢用了。 { k=rmq(y,x); return node[k]; } else { k=rmq(x,y); return node[k]; } } int main() { int n,m,q,a,b,i,w; for(i=0;i<25;i++) mi[i]=1<<i; while(scanf("%d%d",&n,&m)!=EOF) { for(i=1;i<=n;i++) { map[i].clear(); dis[i]=0; vis[i]=0; } for(i=0;i<m;i++) { char c[10]; scanf("%d%d%d%s",&a,&b,&w,c); Node temp; temp.v=b; temp.w=w; map[a].push_back(temp); temp.v=a; map[b].push_back(temp); } int tot=0; memset(vis,0,sizeof(vis)); dfs(tot,1,1,0); rmq_init(tot); scanf("%d",&q); for(i=0;i<q;i++) { scanf("%d%d",&a,&b); printf("%d ",dis[a]+dis[b]-2*dis[lca(a,b)]); } } return 0; }
一种是tarjan离线算法模板
#include <stdio.h> #include <string.h> #include <vector> using namespace std; #define MAXN 50100 #define MAXQ 20000 int N,bcnt,father[MAXN],ance[MAXN],dis[MAXN],res[MAXQ]; struct ENode { int adv,dis; }; struct QNode { int adv,idx; }; vector<ENode> adjlist[MAXN]; vector<QNode> query[MAXN]; bool visited[MAXN]; int color[MAXN]; int find_mfs(int x) { int i,t; for(i=x;father[i]>0;i=father[i]) ; while(x!=i)//把所有节点都指向根 { t=father[x]; father[x]=i; x=t; } return i; } void merge_mfs(int x,int y) { int fx,fy; fx=find_mfs(x); fy=find_mfs(y); if(fx==fy) return; if(father[fx]>father[fy]) //-3>-4 { father[fy]+=father[fx]; father[fx]=fy; } else { father[fx]+=father[fy]; father[fy]=fx; } } void lca_tarjan(int u,int d) { // father[u]=-1; ance[u]=u; visited[u]=true; dis[u]=d; for(size_t j=0;j<adjlist[u].size();j++) { int v=adjlist[u][j].adv; if(!visited[v]) { lca_tarjan(v,d+adjlist[u][j].dis); merge_mfs(u,v); ance[find_mfs(u)]=u; } } color[u]=bcnt; for(size_t k=0;k<query[u].size();k++) { int w=query[u][k].adv; if(color[w]) { if(color[w]==bcnt)//判断是否属于同一集合 { int x=ance[ find_mfs(w) ]; res[query[u][k].idx]=dis[u]+dis[w]-2*dis[x]; } else res[ query[u][k].idx ]=-1; } } } int main() { int M,Q,i,j,k,d; ENode e; QNode q; while(scanf("%d %d",&N,&M)!=EOF) { for(i=1;i<=N;i++) { father[i]=-1; visited[i]=false; color[i]=0; adjlist[i].clear(); query[i].clear(); } for(k=0;k<M;k++) { char c[10]; scanf("%d %d %d%s",&i,&j,&d,c); e.adv=j; e.dis=d; adjlist[i].push_back(e); e.adv=i; adjlist[j].push_back(e); } scanf("%d",&Q); for(k=0;k<Q;k++) { scanf("%d %d",&i,&j); q.adv=j; q.idx=k; query[i].push_back(q); q.adv=i; query[j].push_back(q); } bcnt=0; for(i=1;i<=N;i++) if(!visited[i]) { bcnt++; lca_tarjan(i,0); } for(k=0;k<Q;k++) { printf("%d ",res[k]); } } return 0; }