题意：给定一张n个点，m条边的无向联通图，其中m-n<=20，共q次询问，每次询问求给定两点u，v间的最短路长度
第一眼看见这题的时候，以为有什么神奇的全图最短路算法，满心欢喜的去翻了题解，发现就四个字“树上套环”！
其实这题的提示很明显：m-n<=20！
这说明，如果我们对这个图做一次生成树，那么非树边最多只会有20条！
那么，我们在求任意两点间最短路时，可以分类讨论进行：
①：如果这两点间的最短路只经过树边，那么我们可以直接在树上预处理，利用lca（树上两点距离公式）
②：如果这两点间的最短路会经过非树边，那么由于非树边只有20条，所以产生非树边的点最多只有40个，那这样的话我们可以枚举所有有非树边的点，对全图求最短路，然后在每次询问时枚举每个有非树边的点，每找出一个有非树边的点就去求一遍最短路，最后对找出的所有结果求出最小值即可。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
struct Edge
{
int next;
int to;
ll val;
}edge[];
bool used[];
int num[];
ll dis[][];
int que[];
struct node
{
int lx,rx;
}e[];
struct tt
{
int p;
ll v;
};
bool operator < (tt a,tt b)
{
return a.v>b.v;
}
int head[];
bool vis[];
int deep[];
int cnt=;
int n,m;
void init()
{
memset(head,-,sizeof(head));
memset(dis,0x3f,sizeof(dis));
cnt=;
}
void add(int l,int r,ll w)
{
edge[cnt].next=head[l];
edge[cnt].to=r;
edge[cnt].val=w;
head[l]=cnt++;
}
ll dep[];
int f[][];
void dfs(int x,int fx)
{
deep[x]=deep[fx]+;
f[x][]=fx;
for(int i=head[x];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(to==fx)
{
continue;
}
if(f[to][])
{
continue;
}
dep[to]=dep[x]+edge[i].val;
dfs(to,x);
}
}
void getf()
{
for(int i=;i<=;i++)
{
for(int j=;j<=n;j++)
{
f[j][i]=f[f[j][i-]][i-];
}
}
}
inline int read()
{
int f=,x=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
void diji(int rt,int typ)
{
memset(vis,,sizeof(vis));
dis[rt][typ]=;
priority_queue <tt> M;
tt s;
s.p=rt;
s.v=;
M.push(s);
while(!M.empty())
{
tt uu=M.top();
M.pop();
int u=uu.p;
if(vis[u])
{
continue;
}
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(vis[to])
{
continue;
}
if(dis[to][typ]>dis[u][typ]+edge[i].val)
{
dis[to][typ]=dis[u][typ]+edge[i].val;
tt temp;
temp.p=to;
temp.v=dis[to][typ];
M.push(temp);
}
}
}
}
int LCA(int x,int y)
{
if(deep[x]>deep[y])
{
swap(x,y);
}
for(int i=;i>=;i--)
{
if(deep[f[y][i]]>=deep[x])
{
y=f[y][i];
}
}
if(x==y)
{
return x;
}
int ret;
for(int i=;i>=;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}else
{
ret=f[x][i];
}
}
return ret;
}
int main()
{
n=read(),m=read();
init();
for(int i=;i<=m;i++)
{
int x=read(),y=read(),z=read();
add(x,y,(ll)z);
add(y,x,(ll)z);
e[i].lx=x;
e[i].rx=y;
}
dfs(,);
getf();
for(int i=;i<=m;i++)
{
if(f[e[i].lx][]!=e[i].rx&&f[e[i].rx][]!=e[i].lx)
{
used[e[i].lx]=;
used[e[i].rx]=;
}
}
int cct=;
for(int i=;i<=n;i++)
{
if(used[i])
{
que[++cct]=i;;
diji(i,cct);
}
}
int q=read();
for(int i=;i<=q;i++)
{
int x=read(),y=read();
int f1=LCA(x,y);
ll ret=dep[x]+dep[y]-*dep[f1];
for(int j=;j<=cct;j++)
{
ret=min(ret,dis[x][j]+dis[y][j]);
}
printf("%lld\n",ret);
}
return ;
}