Submission #1163385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163385		altern23	Voting Cities (NOI22_votingcity)	C++20	100 / 100	65 ms	8432 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second

const ll N = 1e3;
const ll INF = 4e18;
const ll MOD = 1e9 + 7;

ll expo(ll a, ll b){
    ll ans = 1;
    for(;b > 0;){
        if(b & 1) ans = (ans * a) % MOD;
        a = (a * a) % MOD;
        b /= 2; 
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll n, e, k; cin >> n >> e >> k;
        vector<vector<ll>> dist(n + 5, vector<ll>(1LL << 5, INF));
        vector<pii> adj[n + 5];

        priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
        for(int i = 1; i <= k; i++){
            ll x; cin >> x;
            dist[x][0] = 0;
            pq.push({0, {x, 0}});
        }

        for(int i = 1; i <= e; i++){
            ll u, v, w; cin >> u >> v >> w;
            adj[v].push_back({u, w});
        }

        for(;!pq.empty();){
            auto [cur, node] = pq.top(); pq.pop();
            if(cur > dist[node.fi][node.sec]) continue;
            for(auto [i, j] : adj[node.fi]){
                if(dist[i][node.sec] > cur + j){
                    dist[i][node.sec] = cur + j;
                    pq.push({dist[i][node.sec], {i, node.sec}});
                }
                for(int add = 0; add < 5; add++){
                    if(!(node.sec & (1LL << add))){
                        if(dist[i][node.sec | (1LL << add)] > cur + j * (10 - (add + 1)) / 10){
                            dist[i][node.sec | (1LL << add)] = cur + j * (10 - (add + 1)) / 10;
                            pq.push({dist[i][node.sec | (1LL << add)], {i, node.sec | (1LL << add)}});
                        }
                    }
                }
            }
        }

        ll q; cin >> q;
        for(int i = 1; i <= q; i++){
            ll s; cin >> s;
            vector<ll> p(5);
            for(int j = 0; j < 5; j++) cin >> p[j];
            ll ans = INF;
            for(ll mask = 0; mask < (1LL << 5); mask++){
                bool ok = 1;
                ll cost = 0;
                for(ll j = 0; j < 5; j++){
                    if(mask & (1LL << j)){
                        if(p[j] == -1){
                            ok = 0;
                            break;
                        }
                        cost += p[j];
                    }
                }
                if(ok){
                    ans = min(ans, cost + dist[s][mask]);
                }
            }

            cout << (ans == INF ? -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