移动迷宫题解

FLY_lai · 2024-07-12 22:17:29 · 题解

【n\le 10】

给爆搜的。不过搜索应该也不好写。

【所有边权相等】

这个题的难点其实就在于有可能通过往回走把原本的下一步变小。但是当所有边权相等的时候，往回走本身就要花费 "原本下一步" 的权值，再走回来必然严格更差。

所以不会走回头路。于是只需要正常跑最短路即可。

【满分做法】

样例二给了提示：303063652 在经过一次变化之后不变。可能会启示选手们思考这个函数本身的不变性质。

观察发现，\dfrac{1}{1-\dfrac{1}{1-\dfrac{1}{1-x}}}=x，也就是说一条道路变化三次之后会变成原来的长度。

既然如此，我们直接分层图，将图分成三层。令 x'=\dfrac{1}{1-x},x''=\dfrac{1}{1-x'}。

对于一条边 (u,v,w)，在新图里变成三条边：(u_1,v_2,w),(u_2,v_3,w'),(u_3,v_1,w'')。然后从 1 跑最短路，答案就是 \min(dist[n_1],dist[n_2],dist[n_3])。

Fun Facts: 这题本来模数是 998，但是我们发现 998 没有一个迭代之后等于自身的不好做提示性样例，所以改了模数。实在太伟大了

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 3e5 + 5;
const ll MOD = 754974721;

ll fpow(ll a, ll b, ll p) {
    ll mul = 1;
    while (b) {
        if (b & 1)
            mul = mul * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return mul;
}
long long inv(long long x, long long mod) { // 计算 x 在模 mod 下的逆元 
    x = (x % mod + mod) % mod;
    return fpow(x, mod - 2, mod);
}

ll n, m;
struct Edge {
    ll to, val;
    Edge(ll t = 0, ll v = 0) {
        to = t, val = v;
    }
};
vector<Edge> e[N];
void addedge(ll u, ll v, ll w) {
    ll ww = inv(1 - w, MOD), www = inv(1 - ww, MOD);
    e[u].push_back(Edge(v + n, w));
    e[u + n].push_back(Edge(v + 2 * n, ww));
    e[u + 2 * n].push_back(Edge(v, www));

    e[v].push_back(Edge(u + n, w));
    e[v + n].push_back(Edge(u + 2 * n, ww));
    e[v + 2 * n].push_back(Edge(u, www));
}

ll dist[N];
bool vis[N];
typedef pair<ll, ll> pii;
void dijkstra(ll s) {
    priority_queue<pii, vector<pii>, greater<pii> > q;
    memset(dist, 0x3f, sizeof dist);
    memset(vis, false, sizeof vis);
    dist[s] = 0;
    q.push(make_pair(dist[s], s));
    while (!q.empty()) {
        ll h = q.top().second;
        q.pop();
        if (vis[h])
            continue;
        vis[h] = true;
        for (ll i = 0; i < e[h].size(); i++)
            if (dist[e[h][i].to] > dist[h] + e[h][i].val) {
                dist[e[h][i].to] = dist[h] + e[h][i].val;
                q.push(make_pair(dist[e[h][i].to], e[h][i].to));
            }
    }
}
int main() {
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
    }
    dijkstra(1);
    cout << min(dist[n * 3], min(dist[n * 2], dist[n]));
    return 0;
}