[CF1051F] Shortest Statement

问题描述

You are given a weighed undirected connected graph, consisting of n vertices and m edges.

You should answer q queries, the i-th query is to find the shortest distance between vertices ui and vi.

输入格式

The first line contains two integers n and m (1≤n,m≤105,m−n≤20)— the number of vertices and edges in the graph.

Next m lines contain the edges: the i-th edge is a triple of integers vi,ui,di (1≤ui,vi≤n,1≤di≤109,ui≠vi). This triple means that there is an edge between vertices ui and vi of weight di. It is guaranteed that graph contains no self-loops and multiple edges.

The next line contains a single integer q (1≤q≤105)— the number of queries.

Each of the next q lines contains two integers ui and vi (1≤ui,vi≤n)— descriptions of the queries.

Pay attention to the restriction m−n ≤ 20

输出格式

Print q lines.

The i-th line should contain the answer to the ii-th query — the shortest distance between vertices ui and vi.

样例输入

3 3

1 2 3

2 3 1

3 1 5

3

1 2

1 3

2 3

样例输出

3

4

1

题目大意

给你一个有n个点,m条边的无向连通图。有q次询问，第i次询问回答从ui到di的最短路的长度。

解析

首先，看到m-n<=20这个条件，意味着边只会比点多20。显然，想要在log(n)时间内查询两点之间的最短路只能是在树上。所以，我们先把原图的最小生成树求出来。两点之间的最短路要么在生成树上，要么会由不在树上的那些非树边得到。非树边最多只有21条，可以对这42个点求单源最短路。对于每次询问，首先查询在树上的最短路，然后枚举非树边的端点，看经过这些非树边是否有更短的路径。

代码

#include <iostream>

#include <cstdio>

#include <queue>

#include <cstring>

#include <cmath>

#include <algorithm>

#define int long long

#define N 200005

#define M 200005

using namespace std;

struct Edge{

	int u,v,w;

}e[M];

int head[N],ver[M*2],nxt[M*2],edge[M*2],l;

int n,m,q,i,j,fa[N],f[N][20],dep[N],d[N],dis[50][N],cnt;

bool use[M];

int read()

{

	char c=getchar();

	int w=0;

	while(c<'0'||c>'9') c=getchar();

	while(c<='9'&&c>='0'){

		w=w*10+c-'0';

		c=getchar();

	}

	return w;

}

void insert(int x,int y,int z)

{

	l++;

	ver[l]=y;

	edge[l]=z;

	nxt[l]=head[x];

	head[x]=l;

}

int my_comp(const Edge &x,const Edge &y)

{

	return x.w<y.w;

}

int find(int x)

{

	if(fa[x]!=x) fa[x]=find(fa[x]);

	return fa[x];

}

void Kruskal()

{

	sort(e+1,e+m+1,my_comp);

	for(int i=1;i<=n;i++) fa[i]=i;

	int cnt=n;

	for(int i=1;i<=m;i++){

		if(cnt==1) break;

		int f1=find(e[i].u),f2=find(e[i].v);

		if(f1!=f2){

			fa[f1]=f2;

			cnt--;

			insert(e[i].u,e[i].v,e[i].w);

			insert(e[i].v,e[i].u,e[i].w);

			use[i]=1;

		}

	}

}

void dfs(int x,int pre)

{

	dep[x]=dep[pre]+1;

	f[x][0]=pre;

	for(int i=head[x];i;i=nxt[i]){

		int y=ver[i];

		if(y!=pre){

			d[y]=d[x]+edge[i];

			dfs(y,x);

		}

	}

}

void init()

{

	dfs(1,0);

	for(int j=0;(1<<(j+1))<=n;j++){

		for(int i=1;i<=n;i++){

			if(f[i][j]==0) f[i][j+1]=0;

			else f[i][j+1]=f[f[i][j]][j];

		}

	}

}

int LCA(int u,int v)

{

	if(dep[u]>dep[v]) swap(u,v);

	int tmp=dep[v]-dep[u];

	for(int i=0;(1<<i)<=tmp;i++){

		if(tmp&(1<<i)) v=f[v][i];

	}

	if(u==v) return u;

	for(int i=log2(1.0*n);i>=0;i--){

		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];

	}

	return f[u][0];

}

int dist(int x,int y)

{

	return d[x]+d[y]-2*d[LCA(x,y)];

}

void Dijkstra(int p,int s)

{

	priority_queue<pair<int,int> > q;

	memset(dis[p],0x3f,sizeof(dis[p]));

	q.push(make_pair(0,s));

	dis[p][s]=0;

	while(!q.empty()){

		int x=q.top().second,d=-q.top().first;

		q.pop();

		if(d!=dis[p][x]) continue;

		for(int i=head[x];i;i=nxt[i]){

			int y=ver[i];

			if(dis[p][y]>dis[p][x]+edge[i]){

				dis[p][y]=dis[p][x]+edge[i];

				q.push(make_pair(-dis[p][y],y));

			}

		}

	}

}

signed main()

{

	n=read();m=read();

	for(i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read();

	Kruskal();

	init();

	for(i=1;i<=m;i++){

		if(!use[i]){

			insert(e[i].u,e[i].v,e[i].w);

			insert(e[i].v,e[i].u,e[i].w);

		}

	}

	for(i=1;i<=m;i++){

		if(!use[i]){

			Dijkstra(++cnt,e[i].u);

			Dijkstra(++cnt,e[i].v);

		}

	}

	q=read();

	for(i=1;i<=q;i++){

		int x=read(),y=read();

		int ans=dist(x,y);

		for(j=1;j<=cnt;j++) ans=min(ans,dis[j][x]+dis[j][y]);//用非树边更新最短路

		cout<<ans<<endl;

	}

	return 0;

}

巴特西