题解：P11898 移动迷宫

分析

一道很不错的分层图最短路题目。

观察 ~~（或打表）~~ 可以发现道路的长度每三个一循环，即

\frac{1}{1-\frac{1}{1-\frac{1}{1-x}}}=x

那么可以对原图建三层的分层图，节点

x

对应的三个节点

x_1=x,x_2=x+n,x_3=x+n\times 2

。若原图有一条从

u

到

v

，长度长度为

w

的边，

w_1=w,w_2=\frac{1}{1-w_1},w_3=\frac{1}{1-w_2}

，则建好的分层图如下：

在分层图上跑最短路，最后输出节点

n

对应的三个节点

n_1,n_2,n_3

距离

1

号节点的距离的最小值即可。

~~好像没有卡 SPFA。~~

Code

CPP

#include<bits/stdc++.h>
#define cst const
#define i64 long long
#define mmax(x,y) ((x)>(y)?(x):(y))
#define mmin(x,y) ((x)<(y)?(x):(y))

using namespace std;

template<typename T>
void read_arr(int n,T *arr){
	for(int i=1;i<=n;++i)cin>>arr[i];
	return;
}

namespace Math{
	i64 ExGcd(cst i64 &a,cst i64 &b,i64 &x,i64 &y){
		if(b==0){x=1,y=0;return a;}
		
		i64 res=ExGcd(b,a%b,y,x);
		y-=a/b*x;
		return res;
	}
	
	//返回值为 a/b%m，本题中模数为质数，可以直接用快速幂，但扩欧更保险
	i64 getmod_frac(cst i64 &a,cst i64 &b,cst i64 &m){
		i64 x=0,y=0;
		i64 tmp=Math::ExGcd(b,m,x,y);
		x=x*a/tmp,x=(x%m+m)%m;
		
		if(a%tmp)return -1;
		return x;
	}
}

constexpr int N=1e5+5;
constexpr i64 mod=754974721;
int n,m;

namespace Graph{
	int tot_edge,hd[N*3];
	struct Edge{int to;i64 val;int lst;}g[N*12];
	void add_edge(cst int &u,cst int &v,cst i64 &w){
		g[++tot_edge]=Edge{v,w,hd[u]};
		hd[u]=tot_edge;
	}
	
	//最短路
	i64 dist[N*3];bool inque[N*3];
	queue<int> que;
	void spfa(int st){
		memset(dist,0x3f,sizeof dist),
		memset(inque,false,sizeof inque);
		while(!que.empty())que.pop();
		
		dist[st]=0,inque[st]=true;
		que.push(st);
		
		while(!que.empty()){
			int frt=que.front();que.pop();
			
			for(int i=hd[frt];~i;i=g[i].lst){
				int ne=g[i].to;i64 val=g[i].val;
				
				if(dist[ne]<=dist[frt]+val)continue;
				dist[ne]=dist[frt]+val;
				if(inque[ne]==false){
					inque[ne]=true;
					que.push(ne);
				}
			}
			
			inque[frt]=false;
		}
	}
}

using namespace Graph;

int main(){
	ios::sync_with_stdio(false),
	cin.tie(nullptr),cout.tie(nullptr);
	
	memset(hd,-1,sizeof hd);
	
	cin>>n>>m;
	for(int _=0;_<m;++_){
		int x1,x2;i64 w1;cin>>x1>>x2>>w1;
		
		//求边权
		i64 w2=Math::getmod_frac(1,1-w1,mod);
		i64 w3=Math::getmod_frac(1,1-w2,mod);
		
		//建分层图
		add_edge(x1+n*0,x2+n*1,w1),add_edge(x2+n*0,x1+n*1,w1),
		add_edge(x1+n*1,x2+n*2,w2),add_edge(x2+n*1,x1+n*2,w2),
		add_edge(x1+n*2,x2+n*0,w3),add_edge(x2+n*2,x1+n*0,w3);
	}
	
	spfa(1);
	
	i64 ans=1e18;
	for(int i=0;i<=2;++i)ans=mmin(ans,dist[n+n*i]);
	
	cout<<ans<<endl;
	return 0;
}

题解：P11898 移动迷宫

文章操作

分析

Code

相关推荐

评论

题解：P11898 移动迷宫