Submission #1177566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177566		VMaksimoski008	Voting Cities (NOI22_votingcity)	C++20	45 / 100	1094 ms	5052 KiB

Main

#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;

signed main() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> imp(k);
    for(int i=0; i<k; i++) cin >> imp[i];

    vector<pair<int, int> > G[n];
    while(m--) {
        int a, b, w; cin >> a >> b >> w;
        G[b].push_back({ a, w });
    }

    int q; cin >> q;
    ll D[n+1][1<<5];
    vector<int> p(5);
    priority_queue<ar<ll, 3>, vector<ar<ll, 3> >, greater<> > pq;

    while(q--) {
        int s; cin >> s;
        for(int i=0; i<5; i++) cin >> p[i];

        for(int i=0; i<n; i++)
            for(int j=0; j<(1<<5); j++) D[i][j] = 1e18;

        for(int x : imp) pq.push({ D[x][(1<<5)-1] = 0, x, (1<<5)-1 });

        while(!pq.empty()) {
            auto [d, u, mask] = pq.top(); pq.pop();
            if(d != D[u][mask]) continue;

            for(auto [v, w] : G[u]) {
                if(D[v][mask] > d + w)
                    pq.push({ D[v][mask] = d + w, v, mask });

                for(int i=0; i<5; i++) {
                    if(p[i] == -1) continue;
                    if(mask & (1 << i)) {
                        int nm = mask ^ (1 << i);
                        ll nd = d + w - (w / 10) * (i+1) + p[i];
                        if(D[v][nm] > nd) {
                            pq.push({ D[v][nm] = nd, v, nm });
                        }
                    }
                }
            }
        }
        
        ll ans = 1e18;
        for(int i=0; i<(1<<5); i++) ans = min(ans, D[s][i]);
        cout << (ans == 1e18 ? -1 : ans) << '\n';
    }
}

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