题目描述
You are given a weighed undirected connected graph, consisting of n vertices and mm 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)
m — 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 vivof 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
Input
3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3
Output
3
4
1
Input
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
Output
7
5
6
7
7
1
2
7
分析
一句话题意：给出一个无向连通图，图中有n个点，m条边，m-n<=20，给出q个询问，每一个询问包含两个整数u和v，对于每一次询问，输出u和v之间的最短路
善良的出题人特别强调了m-n<=20这一个条件
其实如果没有这个条件的话，我们就只能暴力去枚举了
但是既然给出了这个条件，我们就要好好地利用
边数最多只比点数多20，说明这一个图是非常接近一棵树的
如果是树的话，那我们就可以直接用一个LCA维护就可以了
但是这道题中的图要比正常的树多几条边
所以我们可以考虑先来一个最小生成树（随便生成一个树也可以）
这样我们就可以把n-1条边搞定
剩下的m-n+1条边，我们就可以分别以这两条边的两个端点为起点跑最短路
同时把这些点建立一个map映射
这样最短路最多会跑42次
在每一次处理两个点时，我们就可以拿这两个点的LCA
和这两个点到map映射那些点的距离之和中取最小值
需要注意的是，最小生成树和最短路不能用一个图，因为你最小生成树sort之后边就不对应了
所以要提前保存好
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=2e5+50;
map<ll,ll> ma;
struct asd{
ll from,to,next;
ll val;
}b[maxn*2],b2[maxn*2],b3[maxn*2];
ll tot=2,head[maxn];
ll diss[50][maxn];
ll bh;
inline void ad(ll aa,ll bb,ll cc){
b[tot].from=aa;
b[tot].to=bb;
b[tot].next=head[aa];
b[tot].val=cc;
head[aa]=tot++;
}
ll h2[maxn],t2=2;
inline void ad2(ll aa,ll bb,ll cc){
b2[t2].from=aa;
b2[t2].to=bb;
b2[t2].next=h2[aa];
b2[t2].val=cc;
h2[aa]=t2++;
}
ll h3[maxn],t3=2;
inline void ad3(ll aa,ll bb,ll cc){
b3[t3].from=aa;
b3[t3].to=bb;
b3[t3].next=h3[aa];
b3[t3].val=cc;
h3[aa]=t3++;
}
//以上是建边，分别对应原图（跑最短路）、LCA、最小生成树
struct jie{
ll num;
ll dis;
jie(ll aa=0,ll bb=0){
num=aa,dis=bb;
}
bool operator < (const jie& A) const{
return dis>A.dis;
}
};
ll vis[maxn];
void dij(ll xx){
priority_queue<jie> q;
q.push(jie(xx,0));
diss[ma[xx]][xx]=0;
memset(vis,0,sizeof(vis));
while(!q.empty()){
ll now=q.top().num;
q.pop();
if(vis[now]) continue;
vis[now]=1;
for(ll i=head[now];i!=-1;i=b[i].next){
ll u=b[i].to;
if(diss[ma[xx]][u]>b[i].val+diss[ma[xx]][now]){
diss[ma[xx]][u]=b[i].val+diss[ma[xx]][now];
q.push(jie(u,diss[ma[xx]][u]));
}
}
}
}
//dij模板
ll f[maxn][25],dep[maxn];
ll cost[maxn][25];
void dfs(ll now,ll fa,ll da){
dep[now]=dep[fa]+1;
f[now][0]=fa;
cost[now][0]=da;
for(ll i=1;(1<<i)<=dep[now];i++){
f[now][i]=f[f[now][i-1]][i-1];
cost[now][i]=cost[now][i-1]+cost[f[now][i-1]][i-1];
}
for(ll i=h2[now];i!=-1;i=b2[i].next){
ll u=b2[i].to;
if(fa!=u) dfs(u,now,b2[i].val);
}
}
ll Lca(ll aa,ll bb){
if(dep[aa]>dep[bb]) swap(aa,bb);
ll len=dep[bb]-dep[aa],k=0;
ll ans=0;
while(len){
if(len&1){
ans+=cost[bb][k];
bb=f[bb][k];
}
k++,len>>=1;
}
if(aa==bb) return ans;
for(ll i=20;i>=0;i--){
if(f[aa][i]==f[bb][i]) continue;
ans+=cost[aa][i];
ans+=cost[bb][i];
aa=f[aa][i],bb=f[bb][i];
}
return ans+cost[aa][0]+cost[bb][0];
}
//倍增求LCA模板
ll zx[maxn*2],visb[maxn*2];
ll zhao(ll xx){
if(xx==zx[xx]) return xx;
return zx[xx]=zhao(zx[xx]);
}
void bing(ll xx,ll yy){
zx[zhao(xx)]=zhao(yy);
}
bool cmp(asd aa,asd bb){
return aa.val<bb.val;
}
void shu(ll xx){
sort(b3+2,b3+t3,cmp);
for(ll i=0;i<maxn;i++) zx[i]=i;
ll cnt=0;
for(ll i=2;i<t3;i++){
ll x=b3[i].from,y=b3[i].to;
if(zhao(x)!=zhao(y)){
bing(x,y);
ad2(x,y,b3[i].val);
ad2(y,x,b3[i].val);
visb[i]=1;
if(++cnt==xx) return;
}
}
}
//最小生成树模板
int main(){
memset(diss,0x3f,sizeof(diss));
memset(head,-1,sizeof(head));
memset(h2,-1,sizeof(h2));
memset(h3,-1,sizeof(h3));
ll n,m;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
ll aa,bb;
ll cc;
scanf("%lld%lld%lld",&aa,&bb,&cc);
ad(aa,bb,cc),ad(bb,aa,cc);
ad3(aa,bb,cc);
}
shu(n-1);
for(ll i=2;i<t3;i++){
if(!visb[i]){
visb[i]=1;
ll x=b3[i].from,y=b3[i].to;
if(!ma[x]) ma[x]=++bh,dij(x);
if(!ma[y]) ma[y]=++bh,dij(y);
}
}
//把没有加到最小生成树中的边的两个端点拿出来跑最短路
dfs(1,0,0);
ll q;
scanf("%lld",&q);
for(ll i=1;i<=q;i++){
ll aa,bb;
scanf("%d%d",&aa,&bb);
ll ans=Lca(aa,bb);
for(ll i=1;i<=bh;i++){
ans=min(ans,diss[i][aa]+diss[i][bb]);
}
printf("%lld
",ans);
}
return 0;
}