#include<stdio.h>
#include<string.h>
#define MAXN 40000
struct node1
{
	int to,next,val;
}edge[MAXN*9];
struct node2
{
	int from,to,next,index;
}que[MAXN*9];
int n,m,q,cnt1,cnt2;
int head1[MAXN],head2[MAXN],fa[MAXN],visit[MAXN],lca[MAXN],dis[MAXN];
char s[99];
void init()
{
	memset(head1,-1,sizeof(head1));
	memset(head2,-1,sizeof(head2));
	cnt1=cnt2=1;
}
int find(int v)
{
	if(fa[v]==v)
	{
		return fa[v];
	}
	else 
	{
		fa[v]=find(fa[v]);
		return fa[v];
	}
}
void addedge(int from,int to,int val)
{
	edge[cnt1].to=to;
	edge[cnt1].val=val;
	edge[cnt1].next=head1[from];
	head1[from]=cnt1++;
}
void addque(int from,int to,int index)
{
	que[cnt2].from=from;
	que[cnt2].to=to;
	que[cnt2].index=index;
	que[cnt2].next=head2[from];
	head2[from]=cnt2++;
}
void tarjan(int x)
{
	fa[x]=x;
	visit[x]=1;
	int y;
	for(int i=head1[x];i!=-1;i=edge[i].next)
	{
		if(visit[y=edge[i].to]==0)
		{
			dis[y]=dis[x]+edge[i].val;
			tarjan(y);
			fa[y]=x;	
		}
	}
	for(int i=head2[x];i!=-1;i=que[i].next)
	{
		if(visit[y=que[i].to]==1)
		{
			lca[que[i].index]=find(y);
		}
	}
}
void clear()
{
	memset(fa,0,sizeof(fa));
	memset(visit,0,sizeof(visit));
	memset(lca,0,sizeof(lca));
	memset(dis,0,sizeof(dis));
}
int main()
{
	init();
	clear();
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d%s",&a,&b,&c,s);
		addedge(a,b,c);
		addedge(b,a,c);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		addque(a,b,i);
		addque(b,a,i);
	}
	dis[1]=0;
	tarjan(1);
	for(int i=1;i<cnt2;i+=2)
	{
		int a=que[i].from;
		int b=que[i].to;
		int c=que[i].index;
		printf("%d\n",dis[a]+dis[b]-2*dis[lca[c]]);
	}
}

• Re:……悲剧，这题用tarjan怎么做？ (78) 15111005005 2017-07-06 13:28:24