Submission #1281675

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281675		SnowRaven52	Voting Cities (NOI22_votingcity)	C++20	100 / 100	250 ms	14724 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int main() {
    // freopen("main.in", "r", stdin);
	  // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, e, s; cin >> n >> e >> s;

    vector<long long> c; 
    for (int i = 0; i < s; i++) {
        long long v; 
        cin >> v; 
        c.push_back(v);
    }

    vector<vector<pair<long long,long long>>> g(n + 1);
    for (int i = 0; i < e; i++) {
        long long u, v, p; 
        cin >> u >> v >> p; 
        g[v].push_back({ u, p });
    }

    const long long inf = (long long)1e16;
    vector<vector<long long>> d(n + 1, vector<long long>(32, inf));

    using a3 = array<long long, 3>;
    priority_queue<a3, vector<a3>, greater<a3>> pq;
    for (auto &x : c) pq.push({ 0, x, 0 });

    while (!pq.empty()) {
        auto [cost, u, mask] = pq.top(); 
        pq.pop();
        if (d[u][mask] <= cost) continue;
        d[u][mask] = cost;
        for (auto &nx : g[u]) {
            auto [v, w] = nx;
            pq.push({ cost + w, v, mask });
            for (int i = 0; i < 5; i++) {
                if ((mask >> i) & 1) continue;
                long long nw = w * (10 - i - 1) / 10;
                pq.push({ cost + nw, v, mask + (1 << i) });
            }
        }
    }

    long long q; cin >> q;
    while (q--) {
        long long pos; 
        cin >> pos;

        array<long long, 5> price;
        for (int i = 0; i < 5; i++) cin >> price[i];

        if (d[pos][0] == inf) { 
            cout << -1 << endl; 
            continue; 
        }

        long long best = inf;
        for (int m = 0; m < 32; m++) {
            long long cur = d[pos][m];
            bool ok = true;
            for (int i = 0; i < 5; i++) {
                if (((m >> i) & 1) == 0) continue;
                if (price[i] == -1) { ok = false; break; }
                cur += price[i];
            }
            if (!ok) continue;
            if (cur < best) best = cur;
        }
        cout << best << endl;
    }

}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 10 / 10
• Subtask 7: 15 / 15
• Subtask 8: 50 / 50