题解：P11898 移动迷宫

gesong · 2025-03-16 20:12:16 · 题解

题目传送门：P11898 移动迷宫。

思路

首先一个原始长度为 t 的边，收缩一次长度会变为 \dfrac{1}{1-t}，收缩两次长度会变为 \cfrac{1}{1-\frac{1}{1-t}}=\dfrac{t-1}{t}，收缩三次长度变为 \dfrac{1}{1-\frac{t-1}{t}}=t。

根据上面的推导我们发现每一条边的长度在 t,\frac{1}{1-t},\frac{t-1}{t} 中循环，我们就可以设 d_{i,1/2/3} 表示从 1 到 i 点且来到这个点的边的类型为 1/2/3，用类似 dij 的方法转移即可，具体的细节可以看代码。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=754974721,N=1e5+10;
int d[N][4],n,m;
#define pii pair<int,int>
vector<pii >a[N];
map<pii,int>vis;
inline int read(){
    char c=getchar();
    int f=1,ans=0;
    while(c<48||c>57) f=(c==45?f=-1:1),c=getchar();
    while(c>=48&&c<=57) ans=(ans<<1)+(ans<<3)+(c^48),c=getchar();
    return ans*f;
}
void exgcd(int a,int b,int &x,int &y){
    if (b==0) x=1,y=0;
    else exgcd(b,a%b,y,x),y-=a/b*x;
}
inline int inv(int a){
    int x,y;
    exgcd(a,mod,x,y);
    return (x%mod+mod)%mod;
} 
inline int get(int t,int op){
    if (op==1) return t;
    else if (op==2) return inv(1-t+mod);
    return (t-1+mod)*inv(t)%mod;
}
struct nord{
    int u,w,op;
    bool operator <(const nord &x) const{
        return w>x.w;
    }
};
main(){
    n=read(),m=read();
    while(m--){
        int u=read(),v=read(),w=read();
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    for (int i=1;i<=n;i++) d[i][1]=d[i][2]=d[i][3]=1e17;
    d[1][3]=0;
    priority_queue<nord>q;
    q.push({1,0,3});
    while(!q.empty()){
        nord x=q.top();q.pop();
        int u=x.u,op=x.op;
        if (vis.count({u,op})) continue;
        vis[{u,op}]=1;
        for (auto i:a[u]){
            int v=i.first;
            int x=op+1;
            if (x==4) x=1;
            int w=get(i.second,x);
            if (d[v][x]>d[u][op]+w){
                d[v][x]=d[u][op]+w;
                q.push({v,d[v][x],x});
            }
        }
    }
    cout <<min(min(d[n][1],d[n][2]),d[n][3]);
    return 0;
}