Submission #1272981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272981		ken7236	Voting Cities (NOI22_votingcity)	C++20	100 / 100	58 ms	6312 KiB

Main

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

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

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

    int N,E,K;
    if(!(cin>>N>>E>>K)) return 0;
    vector<int> votes(K);
    for(int i=0;i<K;i++) cin>>votes[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}); // reversed graph
    }

    // dist[node][mask] = minimum base cost to a voting city when using 'mask' tickets (costs on edges
    // reflect discounted edge cost when that ticket is applied). This excludes ticket purchase prices.
    vector<array<ll,32>> dist(N);
    for(int i=0;i<N;i++) for(int m=0;m<32;m++) dist[i][m]=INF;

    priority_queue<State, vector<State>, greater<State>> pq;
    for(int t: votes){
        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(const Edge &e: g[u]){
            int v = e.to;
            // no ticket used on this edge
            ll nd = d + e.w;
            if(nd < dist[v][mask]){
                dist[v][mask] = nd;
                pq.push(State{nd,v,mask});
            }
            // try using one unused ticket on this edge (ticket t -> x = t+1)
            for(int t=0;t<5;t++){
                if(mask & (1<<t)) continue;
                int nmask = mask | (1<<t);
                // discounted cost: c * (1 - (t+1)/10) = c*(9-t)/10
                ll nd2 = d + (e.w * (9 - t)) / 10;
                if(nd2 < dist[v][nmask]){
                    dist[v][nmask] = nd2;
                    pq.push(State{nd2,v,nmask});
                }
            }
        }
    }

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

        ll ans = INF;
        for(int mask=0; mask<32; ++mask){
            if((mask & ~avail_mask) != 0) continue; // uses unavailable ticket
            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