dfs找出所有节点所在树及到树根的距离及深度及父亲。
i和j在一棵树上，则最短路为dis[i] dis[j]-dis[LCA(i,j)]*2。
代码语言：javascript复制#include <cstring>
#include <cstdio>
#define N 10005
#define add(u,v,w) e[ cnt]=(edge){v,head[u],w};head[u]=cnt
using namespace std;
struct edge{
int to,next,w;
}e[N<<1];
int head[N],cnt,f[N],dis[N],deep[N],tr[N],t;
int fa(int i,int j){
while(i!=j)
if(deep[i]>deep[j])
i=f[i];
else
j=f[j];
return i;
}
void dfs(int x,int p){
tr[x]=t;
deep[x]=deep[p] 1;
f[x]=p;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==p)continue;
dis[v]=dis[x] e[i].w;
dfs(v,x);
}
}
int main(){
int n,m,c,u,v,w;
while(~scanf("%d%d%d",&n,&m,&c)){
memset(head,0,sizeof head);
memset(f,0,sizeof f);
cnt=t=0;
for(int i=1;i<=m;i ){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
for(int i=1;i<=n;i )
if(f[i]==0){
t ;
dfs(i,0);
}
for(int i=1;i<=c;i ){
scanf("%d%d",&u,&v);
if(tr[u]!=tr[v])
puts("Not connected");
else
printf("%dn",dis[u] dis[v]-dis[fa(u,v)]*2);
}
}
}
