제출 #1272975

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

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4e18;

struct Edge {
    int to;
    ll w;
};

struct State {
    ll dist;
    int node, mask;
    bool operator>(const State& o) const {
        return dist > o.dist;
    }
};

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

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

    vector<vector<Edge>> 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 edges
    }

    int Q; cin >> Q;
    while(Q--){
        int S; ll P[5];
        cin >> S;
        for(int i=0;i<5;i++) cin >> P[i];

        vector<vector<ll>> dist(N, vector<ll>(32, INF));
        priority_queue<State, vector<State>, greater<State>> pq;

        // Multi-source: all voting cities start at dist=0
        for(int t: vote){
            dist[t][0] = 0;
            pq.push(State{0,t,0});
        }

        while(!pq.empty()){
            State cur = pq.top(); pq.pop();
            ll d = cur.dist;
            int u = cur.node;
            int mask = cur.mask;
            if(d!=dist[u][mask]) continue;

            for(auto &e: g[u]){
                int v = e.to;
                // no ticket
                ll nd = d + e.w;
                if(nd < dist[v][mask]){
                    dist[v][mask] = nd;
                    pq.push(State{nd,v,mask});
                }
                // use ticket
                for(int t=0;t<5;t++){
                    if(P[t]==-1) continue;
                    if(mask & (1<<t)) continue;
                    int nmask = mask | (1<<t);
                    ll nd2 = d + (e.w*(10-(t+1)))/10 + P[t];
                    if(nd2 < dist[v][nmask]){
                        dist[v][nmask] = nd2;
                        pq.push(State{nd2,v,nmask});
                    }
                }
            }
        }

        ll ans = INF;
        for(int m=0;m<32;m++) ans = min(ans, dist[S][m]);
        if(ans==INF) cout << -1 << "\n";
        else cout << 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