codeforces - F. The Shortest Statement

F. The Shortest Statement

time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.

Input
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.

Output
Print q lines.

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

Examples
inputCopy
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
outputCopy
3
4
1
inputCopy
8 13
1 2 4
2 3 6
3 4 1
4 5 12
5 6 3
6 7 8
7 8 7
1 4 1
1 8 3
2 6 9
2 7 1
4 6 3
6 8 2
8
1 5
1 7
2 3
2 8
3 7
3 4
6 8
7 8
outputCopy
7
5
6
7
7
1
2
7

题目大意：给你一张图，q次询问，每次回答两个点的最短路。

按照一般的图肯定没法做，但是这张图边不会比点的数量大20以上，于是我们可以想到，这张图可以近似为一棵树，如果是树的话，那么很简单，直接求LCA即可，但是有多余的边，怎么办呢？

我们对于两个点，可以先用LCA求，那么如果更小的最短路，那么一定是通过非树边来更新的，所以我们用非树边更新一次即可，相当于就是预处理出非树边的两个端点，到所有点的最短路，最后都跑一次，取个最小值即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
vector<int> v;
int n,m,q,dst[N],f[N][30],d[45][N],h[N],lg[N];
int head[N],nex[N<<1],to[N<<1],w[N<<1],tot;
inline void add(int a,int b,int c){
	to[++tot]=b; w[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]==fa)	continue;
		if(!h[to[i]])	dst[to[i]]=dst[x]+w[i],dfs(to[i],x);
		else	v.push_back(x),v.push_back(to[i]);
	}
}
inline int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)	
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
void dijkstra(int s,int k){
	priority_queue<pair<int,int> > q;	int vis[N]={0};
	memset(d[k],0x3f,sizeof d[k]);	d[k][s]=0;	q.push({0,s});
	while(q.size()){
		int u=q.top().second;	q.pop();
		if(vis[u])	continue;	vis[u]=1;
		for(int i=head[u];i;i=nex[i]){
			if(d[k][to[i]]>d[k][u]+w[i]){
				d[k][to[i]]=d[k][u]+w[i];	q.push({-d[k][to[i]],to[i]});
			}
		}
	}
}
signed main(){
	scanf("%lld %lld",&n,&m);
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	for(int i=1;i<=m;i++){
		int a,b,c;	scanf("%lld %lld %lld",&a,&b,&c);	add(a,b,c);	add(b,a,c);
	}
	dfs(1,0);	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=0;i<v.size();i++)	dijkstra(v[i],i);
	scanf("%lld",&q);
	while(q--){
		int a,b;	scanf("%lld %lld",&a,&b);
		int res=dst[a]+dst[b]-2*dst[lca(a,b)];
		for(int i=0;i<v.size();i++)	res=min(res,d[i][a]+d[i][b]);
		printf("%lld\n",res);
	}
	return 0;
}