rt蒟蒻太蒻了找不到hack的数据 思路：树剖LCA+Dij

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<list>
#include<map>
#define lson (now<<1)
#define rson (lson|1)
#define mid ((l+r)>>1)
using namespace std;
int h1[100001],c1,h2[100001],c2;
struct edg{
	int next,to,v;
	bool operator > (edg b)
	{
		return v<b.v;
	}
}te[200001],edge[200001];
void add_edge(int u,int v,int w)
{
	edge[++c1].next=h1[u];
	edge[c1].v=w,edge[c1].to=v;
	h1[u]=c1;
}
void add_tree(int u,int v,int w)
{
	te[++c2].next=h2[u];
	te[c2].v=w,te[c2].to=v;
	h2[u]=c2;
}
int ff[100001];
int finds(int x)
{
	return (ff[x]==x)?(x):(ff[x]=finds(ff[x]));
}
void hb(int x,int y)
{
	x=finds(x),y=finds(y);
	ff[x]=y;
}
int dfn[100001],c,vis[100001];
int bj[100001],dep[100001],f[100001];
int hv[100001],spc[100001];
int DFS(int now,int ty)
{
	vis[now]=1;
	int az,lj=0,ma=-1,ma2=0;
	for(int i=h2[now];i;i=te[i].next)
	{
		if(vis[te[i].to]) continue;
		f[te[i].to]=now;
		az=DFS(te[i].to,spc[te[i].to]&ty);
		if(az>ma) ma=az,ma2=i;
		lj+=az;
	}
	hv[now]=ma2;
	return az+1;
}
int hh[100001],hd;
long long hvl[100001];
void dfs(int now,int k)
{
	if(dfn[now]||!now) return;
	dfn[now]=++c;
	dep[now]=k;
	hh[now]=hd;
	dfs(te[hv[now]].to,k+1);
	hvl[now]=hvl[te[hv[now]].to]+te[hv[now]].v;
	for(int i=h2[now];i;i=te[i].next)
	{
		hd=i;
		dfs(te[i].to,k+1);
	}
}
priority_queue<int,vector<int>,greater<int> > q;
int az,rbj[50];
long long dis[50][100001];
int n,m,u,v,w,Q;
long long lca(int a,int b,long long lj)
{
	long long mi=214748364700000ll;
	for(int i=1;i<=az;i++)
	{
		if(te[hh[rbj[i]]].to==te[hh[a]].to) mi=min(abs(hvl[rbj[i]]-hvl[a])+lj+dis[i][b],mi);
		if(te[hh[rbj[i]]].to==te[hh[b]].to) mi=min(abs(hvl[rbj[i]]-hvl[b])+lj+dis[i][a],mi);
	}
	if(te[hh[a]].to==te[hh[b]].to) return min(mi,abs(hvl[a]-hvl[b])+lj);
	return min(mi,(dep[te[hh[a]].to]>dep[te[hh[b]].to])?lca(f[te[hh[a]].to],b,lj+hvl[te[hh[a]].to]-hvl[a]+te[hh[a]].v):lca(a,f[te[hh[b]].to],lj+hvl[te[hh[b]].to]-hvl[b]+te[hh[b]].v));
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) ff[i]=i;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
		add_edge(v,u,w);
		if(finds(u)!=finds(v))
		{
			hb(u,v);
			add_tree(u,v,w);
			add_tree(v,u,w);
		} else spc[u]=spc[v]=1;
	}
	DFS(1,0);
	te[0].to=1,te[0].v=0;
	dfs(1,1);
	for(int i=1;i<=40;i++)
		for(int j=1;j<=n;j++) dis[i][j]=214748364700000ll;
	for(int i=1;i<=n;i++)
	{
		if(spc[i])
		{
			memset(vis,0,sizeof(vis));
			bj[i]=++az;
			rbj[az]=i;
			q.push(i);
			dis[az][i]=0;
			vis[i]=1;
			while(!q.empty())
			{
				int now=q.top();
				q.pop();
				for(int j=h1[now];j;j=edge[j].next)
					if(dis[az][now]+edge[j].v<dis[az][edge[j].to])
					{
						dis[az][edge[j].to]=dis[az][now]+edge[j].v;
						if(!vis[edge[j].to]) q.push(edge[j].to);
						vis[edge[j].to]=1;
					}
			}
		}
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&u,&v);
		printf("%lld\n",lca(u,v,0));
	}
	return 0;
}