最短路 | #小红的数组操作(hard version)#

算法解决最短路

注意要对取模

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<LL, int> PII;

const int N = 1e5 + 10, MOD = 998244353;
const LL INF = 1e18;

void solve() {
    int n, p, x, q, y;
    cin >> n >> p >> x >> q >> y;
    LL sum = 0;
    for (int i = 0; i < n; ++i) {
        int v;
        cin >> v;
        sum += v;
    }

    if (sum % n == 0) {
        cout << 0 << '\n';
        return;
    }

    int r = sum % n;
    vector<LL> d(n + 1, INF);
    vector<bool> st(n + 1, false);
    d[r] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> qu;
    qu.push({0, r});

    while (qu.size()) {
        auto [c, u] = qu.top();
        qu.pop();
        if (st[u]) continue;
        st[u] = true;
        int v = (u + x % n) % n;
        LL cost = d[u] + p;
        if (cost < d[v]) {
            d[v] = cost;
            qu.push({d[v], v});
        }
        v = (u - y % n + n) % n;
        cost = d[u] + q;
        if (cost < d[v]) {
            d[v] = cost;
            qu.push({d[v], v});
        }
    }

    LL ans = d[0];
    if (ans == INF) ans = -1;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();

    return 0;
}