CF1932G(exgcd+dijkstra)WA#3求调

Question

rt，WA在#3的第二个测试点

# pragma GCC optimize("Ofast,no-stack-protector")

# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair <int, int> pii;

const ll inf = 1e18;

struct node {

    int x;

    ll dis;

    bool operator < (const node& t) const {

        return dis > t.dis;

    }

} ;

ll exgcd (ll a, ll b, ll& x, ll& y) {

    if (! b) {

        x = 1, y = 0;

        return a;

    }

    ll g = exgcd (b, a % b, x, y), tmp = x;

    x = y, y = tmp - a / b * y;

    return g;

}

int t, n, m, x, y;

ll h, l[100005], s[100005], dis[100005], a, b, w, ans1, ans2, g;

vector <int> v[100005];

priority_queue <node> q;

ll exg (ll a, ll b, ll c) {

    if (a < 0)
        a = -a, c = -c;

    g = exgcd (a, b, ans1, ans2);

    if (c % g)
        return inf;

    b /= g, c /= g;

    return (ans1 * c % b + b) % b;

}

ll bfs () {

    fill (dis + 2, dis + n + 1, inf);

    q.push ({1, 0});

    while (! q.empty ()) {

        node t = q.top ();
//        cout << t.x << ':' << t.dis << ' ' << (t.dis * s[t.x] + l[t.x]) % h << '\n';
        if (t.x == n) {

            while (! q.empty ())
                q.pop ();

            return t.dis;

        }

        q.pop ();

        for (int& i : v[t.x]) {

            w = exg (s[i] - s[t.x], h, t.dis * (s[t.x] - s[i]) + l[t.x] - l[i]) + 1;

            if (t.dis + w < dis[i])
                q.push ({i, dis[i] = t.dis + w});

        }

    }

    return -1;

}

int main () {

    ios::sync_with_stdio (0);

    cin.tie (0);

    cout.tie (0);

    cin >> t;

    while (t --) {

        cin >> n >> m >> h;

        for (int i = 1; i <= n; ++ i)
            cin >> l[i], v[i].clear ();

        for (int i = 1; i <= n; ++ i)
            cin >> s[i];

        while (m --) {

            cin >> x >> y;

            v[x].emplace_back (y);

            v[y].emplace_back (x);

        }

        cout << bfs () << '\n';

    }

    return 0;

}
/*
1
5 5 563619253
434499018 150448679 82645068 448213607 182107214
527639525 517489084 380964254 72412175 483680857
1 3
5 4
4 2
4 3
1 2

537455327
*/

Answer 1

引自免费微信小程序：皆我百晓生。

请检查你的代码在处理大整数除法或取模运算时是否正确，确保在计算过程中没有溢出或者精度丢失。