欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

POJ1986,Distance Queries(LCA)

程序员文章站 2022-05-27 16:15:23
...

这道题可以用LCA做出来,虽然最短路可以做出来,但是询问次数很多,每询问一次就求一次最短路的话,时间开销是很大的。
这里我是用LCA转化为RMQ求出来,需要注意的一点就是题所给的图可能不是连通的,所以在DFS的时候要稍作改变。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+5;
int depth[2*maxn],id[2*maxn],in[maxn],num;
int dp[2*maxn][15],dis[maxn];	//dis[i]是记录根到i节点的最短距离
bool vis[maxn];	//vis[i]标记i节点是否访问过
struct Edge
{
	int v,cost;
	Edge(int v,int cost) { this->v=v; this->cost=cost; };
};
vector<Edge> G[maxn];

void addedge(int u,int v,int w)
{
	G[u].push_back( Edge(v,w) );
	G[v].push_back( Edge(u,w) );
}

void DFS(int u,int pre,int d)
{
	id[++num]=u;
	in[u]=num;
	depth[num]=d;
	vis[u]=1;
	for(int i=0;i<G[u].size();++i)
	{
		Edge e=G[u][i];
		if(!vis[e.v])
		{
			dis[e.v]=dis[u]+e.cost;
			DFS(e.v,u,d+1);
			id[++num]=u;
			depth[num]=d;
		}
	}
}

void init(int n)
{
	for(int i=1;i<=n;++i)	dp[i][0]=i;
	for(int j=1;(1<<j)<=n;++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
		{
			int a=dp[i][j-1], b=dp[i+(1<<(j-1))][j-1];
			if(depth[a]<depth[b])	dp[i][j]=a;
			else dp[i][j]=b;
		}
}

int RMQ(int l,int r)
{
	int k=0;
	while((1<<(k+1))<=r-l+1)	++k;
	int a=dp[l][k], b=dp[r-(1<<k)+1][k];
	return depth[a]<depth[b]? a:b;
}

int LCA(int u,int v)
{
	int l,r;
	l=in[u]; r=in[v];
	if(l>r)	swap(l,r);
	return id[RMQ(l,r)];
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int u,v,w;	char s[10];
		scanf("%d%d%d%s",&u,&v,&w,s);
		addedge(u,v,w);
	}
	num=0;
	for(int i=1;i<=n;++i)	vis[i]=0;
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])
		{
			dis[i]=0;	//根到根的距离为0
			DFS(i,-1,1);
		}
	}
	init(2*n-1);
	int k;
	scanf("%d",&k);
	while(k--)
	{
		int u,v;
		scanf("%d%d",&u,&v);
		int lca=LCA(u,v);
		printf("%d\n",dis[u]+dis[v]-2*dis[lca]);	
	}
	return 0;
}
相关标签: LCA RMQ