和原来的HDOJ 上一样的，看题目意思就是一棵树，故用LCA，跟方向没关系。
代码：
#include<iostream>#include<string.h>#define maxn 100005using namespace std;struct Edge{int v,w,next;} e[2*maxn],qe[maxn];bool visit[maxn];int dist[maxn],f[maxn],size,qsize;int head[maxn],qhead[maxn];void AddEdge(int a,int b,int c){e[size].v=b;e[size].w=c;e[size].next=head[a];head[a]=size++;}void AddQedge(int a,int b){qe[qsize].v=b;qe[qsize].next=qhead[a];qhead[a]=qsize++;}void init(){size=0; qsize=0;memset(e,0,sizeof(e));memset(qe,0,sizeof(qe));memset(head,-1,sizeof(head));memset(qhead,-1,sizeof(qhead));memset(f,0,sizeof(f));memset(dist,0,sizeof(dist));memset(visit,false,sizeof(visit));}int Find(int x){if( x!=f[x])f[x]=Find(f[x]);return f[x];}void Tarjan(int u){f[u]=u;visit[u]=true;int i,v;for( i=head[u]; i!=-1; i=e[i].next){int v=e[i].v;if( !visit[v]){dist[v]=dist[u]+e[i].w;Tarjan(v);f[v]=u;}}for( i=qhead[u]; i!=-1; i=qe[i].next){int v=qe[i].v;if( visit[v]){qe[i].w=dist[u]+dist[v]-2*dist[Find(v)];qe[i^1].w=qe[i].w;}}}int main(){int n,m,i,a,b,c;char ch;while( scanf("%d%d",&n,&m)!=EOF){init();while( m–){scanf("%d%d%d %c",&a,&b,&c,&ch);AddEdge(a,b,c);AddEdge(b,a,c);}scanf("%d",&c);while( c–){scanf("%d%d",&a,&b);AddQedge(a,b);AddQedge(b,a);}Tarjan(1);for( i=0; i<qsize; i+=2)printf("%d\n",qe[i].w);}return 0;}
，有的事情现在不做，就一辈子也不会做了。
