제출 #1273001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273001		ken7236	Voting Cities (NOI22_votingcity)	C++20	100 / 100	65 ms	6296 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = (1LL<<62);

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,E,K;
    cin >> N >> E >> K;
    vector<int> votes(K);
    for(int i=0;i<K;i++) cin >> votes[i];

    // adjacency list of reversed graph
    vector<vector<pair<int,ll>>> g(N);
    for(int i=0;i<E;i++){
        int u,v; ll c;
        cin >> u >> v >> c;
        g[v].push_back({u,c}); // reverse the edge
    }

    // dist[node][mask] = minimum cost to reach any voting city using ticket mask
    static ll dist[5005][32];
    for(int i=0;i<N;i++) for(int m=0;m<32;m++) dist[i][m]=INF;

    // priority_queue stores (dist, node, mask)
    typedef tuple<ll,int,int> T;
    priority_queue<T, vector<T>, greater<T>> pq;

    // multi-source: start from all voting cities with mask=0
    for(int t: votes){
        dist[t][0] = 0;
        pq.push(T(0,t,0));
    }

    // Dijkstra over state space
    while(!pq.empty()){
        ll d; int u,mask;
        tie(d,u,mask) = pq.top(); pq.pop();
        if(d != dist[u][mask]) continue;

        for(auto &ed: g[u]){
            int v = ed.first;
            ll w = ed.second;

            // case 1: don't use any ticket
            ll nd = d + w;
            if(nd < dist[v][mask]){
                dist[v][mask] = nd;
                pq.push(T(nd,v,mask));
            }

            // case 2: try using one unused ticket on this edge
            for(int t=0;t<5;t++){
                if(mask & (1<<t)) continue; // already used this ticket
                int nmask = mask | (1<<t);
                // discount: type (t+1) = reduce cost by (t+1)*10%
                ll nd2 = d + (w * (9 - t)) / 10;
                if(nd2 < dist[v][nmask]){
                    dist[v][nmask] = nd2;
                    pq.push(T(nd2,v,nmask));
                }
            }
        }
    }

    int Q; cin >> Q;
    while(Q--){
        int S; ll P[5];
        cin >> S;
        int avail = 0;
        for(int i=0;i<5;i++){
            cin >> P[i];
            if(P[i] != -1) avail |= (1<<i);
        }

        ll ans = INF;
        for(int mask=0;mask<32;mask++){
            // skip masks that use unavailable tickets
            if((mask & ~avail) != 0) continue;
            ll base = dist[S][mask];
            if(base >= INF) continue;
            ll sumP=0;
            for(int t=0;t<5;t++) if(mask&(1<<t)) sumP += P[t];
            ans = min(ans, base + sumP);
        }

        if(ans>=INF) cout << -1 << "\n";
        else cout << ans << "\n";
    }
    return 0;
}

• 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