Submission #1177568

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177568		VMaksimoski008	Voting Cities (NOI22_votingcity)	C++20	100 / 100	70 ms	8120 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;

    
    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);
                    if(D[v][nm] > nd)
                        pq.push({ D[v][nm] = nd, v, nm });
                }
            }
        }
    }


    while(q--) {
        int s; cin >> s;
        for(int i=0; i<5; i++) cin >> p[i];
        
        ll ans = 1e18;
        for(int i=0; i<(1<<5); i++) {
            ll shit = 0;
            for(int j=0; j<5; j++)
                if((i & (1 << j)) == 0) shit += (p[j] == -1 ? 1e18 : p[j]);
            ans = min(ans, D[s][i] + shit);
        }
        cout << (ans >= 1e18 ? -1 : ans) << '\n';
    }
}

• 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