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;
}
