题意：给你N个点M条边，M-N<=20,有1e5个询问，询问两点的最短距离。保证没有自环和重边。
题解：连题目都在提示你这个20很有用，所以如果是颗树的话那任意两点的最短距离就是求一下lca搞一搞的问题。所以可以先求出最小生成树，那么会剩下最多42个点，我们知道非树边可能更优，所以对于每条非树边对应的两个点跑一遍dij，尝试更新答案ans=min(ans,dis[i][u]+dis[i][v])。正确性：可能通过多条非树边？在跑dij时其实已经处理出了最短的路，如果是通过多条非树边更优，那么它记录的就是这样的值。为什么这个题别人的代码那么短。。。
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ls x<<1
#define rs x<<1|1
#define ull unsigned long long
#define _mp make_pair
#define ldb long double
using namespace std;
const int maxn=1e5+100;
const ll inf=1e18;
int bcg[maxn];
struct Edge
{
int u,v,nxt;
ll w;
}edge[maxn*2],edge1[maxn*2];
vector<Edge>vec[maxn];
struct Node{
ll p;
int v;
friend bool operator<(Node a,Node b)
{
return a.p>b.p;
}
Node(){}
Node(ll x,int y){p=x,v=y;}
};
int head[maxn],head1[maxn];
ll deep[maxn];
int depth[maxn];
int bian[maxn*2];
ll dis[50][maxn];
int lca[maxn][25];
int vis[maxn];
int cnt,cnt1,tot;
int n,m;
int findd(int x)
{
return bcg[x]==x?bcg[x]:bcg[x]=findd(bcg[x]);
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
void add_e1(int x,int y,ll w)
{
++cnt1;edge1[cnt1].u=x;edge1[cnt1].v=y;edge1[cnt1].w=w;edge1[cnt1].nxt=head1[x];head1[x]=cnt1;
}
void add_e(int x,int y,ll w)
{
++cnt;edge[cnt].u=x;edge[cnt].v=y;edge[cnt].w=w;edge[cnt].nxt=head[x];head[x]=cnt;
}
int merges(int x,int y)
{
int xx=findd(x);
int yy=findd(y);
if(xx!=yy)
{
bcg[xx]=yy;
return 1;
}
return 0;
}
void init()
{
cnt=cnt1=0;
tot=0;
memset(deep,0,sizeof(deep));
memset(head,0,sizeof(head));
memset(head1,0,sizeof(head1));
}
void dfs(int x,int ff)
{
lca[x][0]=ff;
for(int i=1;i<=20;i++)lca[x][i]=lca[lca[x][i-1]][i-1];
for(int i=head[x];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(v==ff)continue;
deep[v]=deep[x]+edge[i].w;
depth[v]=depth[x]+1;
dfs(v,x);
}
}
int LCA(int x,int y)
{
if(depth[x]<depth[y])swap(x,y);
int ff=depth[x]-depth[y];
for(int i=20;i>=0;i--)
{
if(ff&(1<<i))x=lca[x][i];
}
if(x==y)return y;
for(int i=20;i>=0;i--)
{
if(lca[x][i]!=lca[y][i])x=lca[x][i],y=lca[y][i];
}
return lca[y][0];
}
priority_queue<Node>que;
void dij(int id,int x)
{
for(int i=0;i<=n+4;i++)
{
dis[id][i]=inf;
vis[i]=0;
}
dis[id][x]=0;
while(!que.empty())que.pop();
que.push(Node(0,x));
while(!que.empty())
{
Node vv=que.top();que.pop();
if(vis[vv.v]||vv.p>dis[id][vv.v])continue;
vis[vv.v]=1;
for(int i=0;i<(int)vec[vv.v].size();i++)
{
Edge k=vec[vv.v][i];
int sw=k.v;
if(vis[sw])continue;
if(dis[id][sw]>dis[id][vv.v]+k.w)
{
dis[id][sw]=dis[id][vv.v]+k.w;
que.push(Node(dis[id][sw],sw));
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int u,v;
ll w;
init();
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&u,&v,&w);
add_e1(u,v,w);
vec[u].push_back((Edge){u,v,0,w});
vec[v].push_back((Edge){v,u,0,w});
}
sort(edge1+1,edge1+cnt1+1,cmp);
for(int i=1;i<=n+4;i++)bcg[i]=i;
for(int i=1;i<=cnt1;i++)
{
int x=edge1[i].u,y=edge1[i].v;
if(merges(x,y))
{
add_e(x,y,edge1[i].w);
add_e(y,x,edge1[i].w);
}
else
{
bian[++tot]=x;
bian[++tot]=y;
}
}
depth[1]=0;
deep[1]=0;
dfs(1,0);
sort(bian+1,bian+1+tot);
int sz=unique(bian+1,bian+1+tot)-(bian+1);
for(int i=1;i<=sz;i++)
{
dij(i,bian[i]);
}
int q;
scanf("%d",&q);
int x,y;
while(q--)
{
scanf("%d%d",&x,&y);
ll ans=inf;
int pq=LCA(x,y);
ans=deep[x]+deep[y]-2*deep[pq];
for(int i=1;i<=sz;i++)
{
ans=min(ans,dis[i][x]+dis[i][y]);
}
cout<<ans<<"
";
}
return 0;
}