[CF1051F] The Shortest Statement

题目

原题地址

解说

又没时间了所以我说简洁一些。
看上去是裸的最短路，但是数据范围肯定不允许。这时候发现题目中特意强调了(m,n)之差不超过(20)，这一定有用处。那么我们可以找一棵最小生成树，剩下还连着最多(21)条边。所以若两个点都在树上直接(LCA)解决，否再要经过外面的边，(20)不算太大暴力枚举解决。
——引自https://www.luogu.com.cn/blog/aaronlee/solution-cf1051f

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
namespace StandardIO{
	template<typename T>inline void read(T &x){
		x=0;T f=1;char c=getchar();
		for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
		for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0';
		x*=f;
	}
	template<typename T>inline void write(T x){
		if(x<0)putchar('-'),x*=-1;
		if(x>=10)write(x/10);
		putchar(x%10+'0');
	}
}
using namespace StandardIO;
namespace Solve{
	#define int long long
	const int N=100100;
	const int INF=2147483647;
	int n,m,p;
	int cnt;
	int head[N];
	struct node{
		int to,val,next;
	}edge[N<<1];
	template<typename T>inline void add(T a,T b,T c){
		edge[++cnt].to=b,edge[cnt].val=c,edge[cnt].next=head[a],head[a]=cnt;
	}
	struct qnode{
		int key,val;
		bool operator < (qnode x)const{
			return val>x.val;
		}
	};
	int top;
	int vis[N],fa[N][23],dist[N],dep[N],q[N];
	int dis[50][N];
	inline void dfs(int now,int father){
		vis[now]=1,fa[now][0]=father;
		for(register int i=head[now];i;i=edge[i].next){
			int to=edge[i].to;
			if(to==father)continue;
			if(vis[to])q[++top]=now,q[++top]=to;
			else{
				dep[to]=dep[now]+1,dist[to]=dist[now]+edge[i].val;
				dfs(to,now);
			}
		}
	}
	template<typename T>inline T lca(T x,T y){
		if(dep[x]<dep[y])swap(x,y);
		for(register int i=19;i>=0;--i){
			if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
		}
		if(x==y)return x;
		for(register int i=19;i>=0;--i){
			if(fa[x][i]!=fa[y][i]){
				x=fa[x][i],y=fa[y][i];
			}
		}
		return fa[x][0];
	}
	inline void dijkstra(int now){
		memset(dis[now],63,sizeof(dis[now]));
		memset(vis,0,sizeof(vis));
		priority_queue<qnode>Q;
		dis[now][q[now]]=0;
		Q.push((qnode){q[now],0});
		while(!Q.empty()){
			int tmp=Q.top().key;Q.pop();
			if(vis[tmp])continue;
			vis[tmp]=1;
			for(register int i=head[tmp];i;i=edge[i].next){
				int to=edge[i].to;
				if(!vis[to]&&dis[now][tmp]+edge[i].val<dis[now][to]){
					dis[now][to]=dis[now][tmp]+edge[i].val;
					Q.push((qnode){to,dis[now][to]});
				}
			}
		}
	}
	inline void solve(){
		read(n),read(m);
		for(register int i=1;i<=m;++i){
			int a,b,c;
			read(a),read(b),read(c);
			add(a,b,c),add(b,a,c);
		}
		dep[1]=1,dfs(1,0);
		for(register int j=1;j<=19;++j){
			for(register int i=1;i<=n;++i){
				fa[i][j]=fa[fa[i][j-1]][j-1];
			}
		}
		sort(q+1,q+top+1);top=unique(q+1,q+top+1)-q-1;
		for(register int i=1;i<=top;++i)dijkstra(i);
		read(p);
		while(p--){
			int x,y;
			read(x),read(y);
			int ans=dist[x]+dist[y]-2*dist[lca(x,y)];
			for(register int i=1;i<=top;++i)ans=min(ans,dis[i][x]+dis[i][y]);
			write(ans),putchar('
');
		}
	}
}
using namespace Solve;
#undef int
int main(){
	solve();
}

幸甚至哉，歌以咏志。