这题目跟杭电的2586很像，呵呵，应该说，本来这道是先做的，但是LAC不会，所以就先做了那道基础题
好悲剧呀，在代码里面加了一个测试输出，结果忘记删了，还固执的贡献了几个WA，题目中给的方向是没用的，读进来就可以
因为代码基本一样，具体解释见hdu2586
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 40010 struct node { int vex,next,dis; }g[MAXN*2],q[10010*2]; int f[MAXN],first[MAXN],head[MAXN],n,m; int visited[MAXN],away[MAXN]; int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void add(int v,int w,int d,int &j) { g[j].dis=d; g[j].vex=w; g[j].next=first[v]; first[v]=j++; } void add2(int v,int w,int &j) { q[j].dis=-1; q[j].vex=w; q[j].next=head[v]; head[v]=j++; } void DFS(int v,int d) { visited[v]=1; f[v]=v; away[v]=d; int i; for(i=head[v];i!=-1;i=q[i].next) { if(visited[q[i].vex]) { q[i].dis=away[v]+away[q[i].vex]-2*away[find(q[i].vex)]; } } for(i=first[v];i!=-1;i=g[i].next) { if(!visited[g[i].vex]) { DFS(g[i].vex,d+g[i].dis); f[g[i].vex]=v; } } } int main() { int i,j,a,b,d,k; char ch[2]; scanf("%d %d",&n,&m); memset(first,-1,sizeof(first)); memset(head,-1,sizeof(head)); memset(visited,0,sizeof(visited)); for(i=1,j=0;i<=m;i++) { scanf("%d %d %d %s",&a,&b,&d,ch); add(a,b,d,j); add(b,a,d,j); } scanf("%d",&k); for(i=j=0;i<k;i++) { scanf("%d %d",&a,&b); /*if(a==b) { q[j].dis=0; j+=2; continue; }*/ add2(a,b,j); add2(b,a,j); } DFS(1,0); for(i=j=0;i<k;i++,j+=2) { if(q[j].dis!=-1) printf("%d\n",q[j].dis); else printf("%d\n",q[j+1].dis); } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/05/08/2040301.html
相关资源：数据结构—成绩单生成器