Submission #1283386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283386		nathlol2	Voting Cities (NOI22_votingcity)	C++20	100 / 100	955 ms	3636 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 5;
int n, m, k, q, t[N], rv[N], dist[N][32];
vector<pair<int, int>> g[N];
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m >> k;
    for(int i = 0;i<k;i++) cin >> t[i], rv[t[i]] = 1;
    for(int i = 0;i<m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
    }
    int q;
    cin >> q;
    while(q--){
        for(int i = 0;i<n;i++){
            for(int j = 0;j<32;j++){
                dist[i][j] = LLONG_MAX;
            }
        }
        int st, p[5], c = 0;
        cin >> st;
        for(int i = 0;i<5;i++){cin >> p[i]; if(p[i] != -1) c |= (1 << i);}
        for(int i = 0;i<32;i++){
            if((i & (~c)) != 0) continue;
            int pr = 0;
            if((i & 1)) pr += p[0];
            if((i & 2)) pr += p[1];
            if((i & 4)) pr += p[2];
            if((i & 8)) pr += p[3];
            if((i & 16)) pr += p[4];
            pq.push({pr, {st, i}});
            dist[st][i] = pr;
        }
        while(!pq.empty()){
            auto [d, P] = pq.top();
            pq.pop();
            auto [u, s] = P;
            if(rv[u]){
                cout << d << '\n';
                goto ee;
            }
            if(d > dist[u][s]) continue;
            for(auto [v, w] : g[u]){
                if(d + w < dist[v][s]){
                    dist[v][s] = d + w;
                    pq.push({dist[v][s], {v, s}});
                }
                if(s & 1){
                    if(d + (w * 9) / 10 < dist[v][s - 1]){
                        dist[v][s - 1] = d + (w * 9) / 10;
                        pq.push({dist[v][s - 1], {v, s - 1}});
                    }
                }
                if(s & 2){
                    if(d + (w * 8) / 10 < dist[v][s - 2]){
                        dist[v][s - 2] = d + (w * 8) / 10;
                        pq.push({dist[v][s - 2], {v, s - 2}});
                    }
                }
                if(s & 4){
                    if(d + (w * 7) / 10 < dist[v][s - 4]){
                        dist[v][s - 4] = d + (w * 7) / 10;
                        pq.push({dist[v][s - 4], {v, s - 4}});
                    }
                }
                if(s & 8){
                    if(d + (w * 6) / 10 < dist[v][s - 8]){
                        dist[v][s - 8] = d + (w * 6) / 10;
                        pq.push({dist[v][s - 8], {v, s - 8}});
                    }
                }
                if(s & 16){
                    if(d + (w * 5) / 10 < dist[v][s - 16]){
                        dist[v][s - 16] = d + (w * 5) / 10;
                        pq.push({dist[v][s - 16], {v, s - 16}});
                    }
                }
            }
        }
        cout << -1 << '\n';
        continue;
        ee:
        while(!pq.empty()) pq.pop();
    }
}

• 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