Rockdu's Blog

InputInput consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.OutputFor each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.Sample Input

5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5

Sample Output

Not connected
6

本题其实就是维护森林上的倍增LCA。对于每一棵树维护倍增信息。对于整个森林我们用并查集维护一下连通性就可以了。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=20000+100;
const int max2=20;
struct edge
{
	int v,w;
	int next;
}e[maxn*2];

int head[maxn];
int fa[maxn];
int d[maxn];
bool vis[maxn];
int dc[maxn];
int p[maxn][max2+5];
int n,m,qn;
int edk;

void init(int n)
{
	for(int i=1;i<=n;i++)
		fa[i]=i;
}

int find(int a)
{
	if(fa[a]==a) return a;
	return fa[a]=find(fa[a]);
}

void combine(int a,int b)
{
	a=find(a);
	b=find(b);
	fa[a]=b;
}

void adde(int u,int v,int w)
{
	e[++edk].w=w;
	e[edk].v=v;
	e[edk].next=head[u];
	head[u]=edk;
}

void dfs(int u,int fa,int ec)
{
	d[u]=d[fa]+1;
	dc[u]=dc[fa]+ec;
	p[u][0]=fa;
	for(int i=1;i<=max2;i++)
		p[u][i]=p[p[u][i-1]][i-1];
	
	for(int i=head[u];i!=-1;i=e[i].next)
	{
		int v=e[i].v;
		if(v!=fa)
			dfs(v,u,e[i].w);
	}
}

int lca(int a,int b)
{
	if(d[a]<d[b]) swap(a,b);
	for(int i=max2;i>=0;i--)
		if(d[a]-(1<<i)>=d[b])
			a=p[a][i];

	if(a==b) return a;
	for(int i=max2;i>=0;i--)
		if(p[a][i]!=p[b][i])
			{
				a=p[a][i];
				b=p[b][i];
			}
	return p[a][0];
}

int main()
{
	while(scanf("%d%d%d",&n,&m,&qn)==3)
	{
		memset(vis,0,sizeof(vis));
		memset(p,0,sizeof(p));
		memset(d,0,sizeof(d));
		memset(dc,0,sizeof(dc));
		memset(head,-1,sizeof(head));
		edk=0;
		init(n);
		for(int i=1;i<=m;i++)
			{
				int a,b,c;
				scanf("%d%d%d",&a,&b,&c);
				adde(a,b,c);
				adde(b,a,c);
				combine(a,b);
			}
		for(int i=1;i<=n;i++)
		if(!vis[find(i)])
		{
			vis[find(i)]=1;
			dfs(i,0,0);
		}
		for(int i=1;i<=qn;i++)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(find(a)!=find(b))
				{
					printf("Not connected\n");
					continue;
				}
			int t=lca(a,b);
			printf("%d\n",dc[a]-dc[t]+dc[b]-dc[t]);
		}
	}
	return 0;
}