How far away ？ HDU

本文主要是介绍How far away ？ HDU，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

LCA应用求最短路

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=40005;
int T,n,m,ans,tot;
struct node{
	int to,next,w;
}edge[N<<1];
int head[N],dep[N];
int f[N][30],dis[N][30];
void init(){
	tot=0;
	memset(edge,0,sizeof(edge));
	memset(head,-1,sizeof(head));
	memset(dep,0,sizeof(dep));
	memset(dis,0,sizeof(dis));
}
void add(int u,int v,int w){
	edge[tot].to=v;
	edge[tot].next=head[u];
	edge[tot].w=w;
	head[u]=tot++;
}
void dfs(int u,int fa){
	f[u][0]=fa; dep[u]=dep[fa]+1;
	for(int j=1;(1<<j)<=dep[u];j++){
		f[u][j]=f[f[u][j-1]][j-1];
		dis[u][j]=dis[u][j-1]+dis[f[u][j-1]][j-1];
	}
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(v!=fa){
			dis[v][0]=edge[i].w;
			dfs(v,u);
		}
	} 
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	if(dep[u]!=dep[v]){
		for(int j=20;j>=0;j--){
			if(dep[f[u][j]]>=dep[v]){
				ans+=dis[u][j];
				u=f[u][j];
			}
		}
	}
	if(u==v) return ans;
	for(int j=20;j>=0;j--){
		if(f[u][j]!=f[v][j]){
			ans+=dis[u][j];
			ans+=dis[v][j];
			u=f[u][j];
			v=f[v][j];
		}
	}
	return ans+dis[u][0]+dis[v][0];
}
int main(){
	scanf("%d",&T);
	while(T--){
		init();
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<n;i++){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z); add(y,x,z);
		}
		dfs(1,0);
		for(int i=1;i<=m;i++){
			ans=0;
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",lca(x,y));
		}
	}
	return 0;
}

这篇关于How far away ？ HDU的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！