CF1051F The Shortest Statement Dijkstra+生成树

题意：

给定一张(n)个点(m)条边的图，(q)次询问两点之间的最短路

范围&性质：(1le n,m,qle 10^5,1le m-nle 20)

分析：

题面及其简洁，所以我们发现唯一显得很特别的一个条件就是(1le m-nle 20)

,这个条件说明了什么，说明了整张图可以看做一棵树上多挂了几条边，所以我们只要对于特殊边所在的点跑一遍最短路，因为任意点对要么从树上走，要么必定经过这些特殊边，所以至多对40个点跑一遍最短路，复杂度是(O( 能过 ))

代码：

#include<bits/stdc++.h>
#define mk(x,y) make_pair(x,y)
using namespace std;

namespace zzc
{
	const int maxn = 1e5+5;
	int n,m,cnt=1,q;
	int head[maxn],dep[maxn],fa[maxn][25];
	bool vis[maxn],ins[maxn];
	long long dis[50][maxn],tdis[maxn];
	
	vector<int> res;
	
	struct edge
	{
		int frm,to,nxt,dis;
		bool flag;
	}e[(maxn<<1)+100];
	
	void add(int u,int v,int w)
	{
		e[++cnt].to=v;
		e[cnt].frm=u;
		e[cnt].dis=w;
		e[cnt].nxt=head[u];
		e[cnt].flag=false;
		head[u]=cnt;
	}
	
	void dfs(int u)
	{
	    dep[u]=dep[fa[u][0]]+1;
	    vis[u]=true;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			if(vis[v]) continue;
			e[i].flag=true;
			e[i^1].flag=true;
			fa[v][0]=u;
			tdis[v]=tdis[u]+e[i].dis;
			dfs(v);
		}
	}
	
	void getpre()
	{
		for(int i=1;i<=20;i++)
		{
			for(int j=1;j<=n;j++)
			{
				fa[j][i]=fa[fa[j][i-1]][i-1];
			}
		}
	}
	
	void dijkstra(int st,int id)
	{
		memset(dis[id],0x7f,sizeof(dis[id]));
		memset(vis,false,sizeof(vis));
		priority_queue<pair<long long,int> > q;
		dis[id][st]=0;
		q.push(mk(0,st));
		while(!q.empty())
		{
			int u=q.top().second;
			q.pop();
			if(vis[u]) continue;
			vis[u]=true;
			for(int i=head[u];i;i=e[i].nxt)
			{
				int v=e[i].to;
				if(vis[v]) continue;
				if(dis[id][v]>dis[id][u]+e[i].dis)
				{
					dis[id][v]=dis[id][u]+e[i].dis;
					q.push(mk(-dis[id][v],v));
				}
			}
		}
	}
	
	int lca(int x,int y)
	{
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=20;i>=0;i--)
		{
			if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		}
		if(x==y) return x;
		for(int i=20;i>=0;i--)
		{
			if(fa[x][i]!=fa[y][i])
			{
				x=fa[x][i];
				y=fa[y][i];
			}
		}
		return fa[x][0];
	}
	
	void work()
	{
		int a,b,c;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			add(a,b,c);
			add(b,a,c);
		}
		dfs(1);
		for(int i=2;i<=cnt;i++)
		{
			if(!e[i].flag)
			{
				if(!ins[e[i].frm]) res.push_back(e[i].frm),ins[e[i].frm]=true;
				if(!ins[e[i].to]) res.push_back(e[i].to),ins[e[i].to]=true;
			}
		}
		getpre();
		for(int i=0;i<res.size();i++)
		{
			dijkstra(res[i],i);
		}
		scanf("%d",&q);
		for(int i=1;i<=q;i++)
		{
			scanf("%d%d",&a,&b);
			long long ans=tdis[a]+tdis[b]-2*tdis[lca(a,b)];
			for(int i=0;i<res.size();i++)
			{
				ans=min(ans,dis[i][a]+dis[i][b]);	
			}
			printf("%lld
",ans);
		}
	}
	
}

int main()
{
	zzc::work();
	return 0;
}