原來莫名的超時，稍微改了一下就過了，還是改了的好啊。LCA的Tarjan算法，和原來是一樣的，不過這是個深林不是樹，所以還要用並查集確定的找到每個樹的根，完後再進行Tarjan.和原來的how far away想必多了一個找樹的過程。
代碼：
[cpp]
#include<iostream>
#include<string.h>
using namespace std;
#define maxn 10050
struct Edge
{
int v,w,next;
} e[2*maxn],qe[2000500];
bool visit[maxn];
int dist[maxn],f[maxn],size,qsize,root[maxn];
int head[maxn],qhead[maxn],n;
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,int c)
{
qe[qsize].v=b;
qe[qsize].w=c;
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(dist,0,sizeof(dist));
memset(root,false,sizeof(root));
for(int i=0; i<=n; i++)
f[i]=i;
}
int Find(int x)
{
if( x!=f[x])
f[x]=Find(f[x]);
return f[x];
}
void Union(int x,int y)
{
x=Find(x);
y=Find(y);
if( x!=y)
f[x]=y;
}
void Tarjan(int u)
{
f[u]=u;
visit[u]=true;
int i;
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 m,t,i,a,b,c,j;
while( scanf("%d%d%d",&n,&m,&c)!=EOF){
init();
while( m--){
scanf("%d%d%d",&a,&b,&t);
AddEdge(a,b,t);
AddEdge(b,a,t);
Union(a,b);
}
for( i=1; i<=n; i++) //找樹根的過程，同時確定每個結點所在樹的根節點
root[Find(i)]=true;
while( c--){
scanf("%d%d",&a,&b);
if( f[a]!=f[b]){ //根據原來並查之後的結果判斷如果不在同一顆樹上距離賦為-1.
AddQedge(a,b,-1);
AddQedge(b,a,-1);
}
else{
AddQedge(a,b,0);
AddQedge(b,a,0);
}
}
memset(f,0,sizeof(f));
for( i=1; i<=n; i++){
if( root[i]){ //如果是樹根就進行遍歷
memset(visit,false,sizeof(visit));
Tarjan(i);
}
}
for( i=0; i<qsize; i+=2){ //輸出距離
if( qe[i].w==-1)
printf("Not connected\n");
else
printf("%d\n",qe[i].w);
}
}
return 0;
}
作者：aacm1992
