题解：P11898 移动迷宫

ZesteYdaZ · 2025-03-17 20:28:31 · 题解

分析

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

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

那么可以对原图建三层的分层图，节点 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

#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;
}