제출 #1272410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272410		choed	Voting Cities (NOI22_votingcity)	C++20	0 / 100	52 ms	5532 KiB

Main

#include <bits/stdc++.h>
#define GO_BEYOND ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define plll pair<ll,pll>
using namespace std;

const ll MAXN=5000;
const ll MAXB=32;
vector<pll> edge[MAXN+1];
priority_queue<plll, vector<plll>, greater<plll>> pq;
vector<vector<ll>> mn(MAXN+1, vector<ll>(MAXB, INT_MAX));

void dijkstra(ll c, ll u, ll mask){
    if(c>mn[u][mask])
        return;

    // cout << u << ' ' << c << ' ' << mask << " CURRENT" << endl;

    ll cur, curmask;
    for(auto x: edge[u]){
        curmask=mask;
        cur=c+x.se;
        if(mn[x.fi][curmask] > cur){
            pq.push({cur, {x.fi, curmask}});
            mn[x.fi][curmask]=cur;
        }

        // cout << x.fi << ' ' << x.se << endl;
        for(int i=0; i<5; i++){
            // cout << ((1LL<<i)&mask) << endl;
            if(((1LL<<i)&mask) == 0){
                cur=c+(x.se*(10-i-1)/10);
                curmask=mask+(1LL<<i);
                // cout << cur << ' ' << i+1 << ' ' << curmask << endl;
                if(mn[x.fi][curmask] > cur){
                    pq.push({cur, {x.fi, curmask}});
                    mn[x.fi][curmask]=cur;
                }
            }   
        }
    }
}

void solve(){
    ll n, e, k; cin >> n >> e >> k;
    ll t[k];
    for(int i=0; i<k; i++)
        cin >> t[i];
    
    ll u, v, c;
    for(int i=0; i<e; i++){
        cin >> u >> v >> c;
        edge[u].push_back({v,c});
    }

    for(int j=0; j<k; j++){
        pq.push({0, {t[j], 0}});
        for(int i=0; i<MAXB; i++)
            mn[t[j]][i]=0;
    }
    
    while(!pq.empty()){
        c=pq.top().fi;
        u=pq.top().se.fi;
        v=pq.top().se.se;
        pq.pop();
        dijkstra(c, u, v);
    }

    ll q; cin >> q;
    while(q--){
        ll s, mask=0; cin >> s;
        vector<ll> price(5);
        for(int i=0; i<5; i++){
            cin >> price[i];
            if(price[i]!=-1)
                mask+=(1LL<<i);
        }
        
        ll ans=LLONG_MAX, cur;
        for(int i=0; i<MAXB; i++){
            if((i&mask)==i){
                cur=mn[s][i];
                for(int j=0; j<5; j++){
                    if(((1LL<<j)&i)>0)
                        cur+=price[j];
                }
                ans=min(ans, cur);
            }
            // cout << i << ' ' << cur << endl;
        }
        if(ans==INT_MAX)
            cout << -1;
        else cout << ans;
        cout << endl;
    }
}

/*
g++ sigma.cpp -o a
3 2 1
2
0 1 100
1 2 200
1
0 10 20 1000 2000 -1

2 0 1
1
1
0 -1 -1 -1 -1 -1

6 3 2
4 5
0 4 100
1 4 200
2 5 300
4
0 -1 -1 -1 -1 -1
1 20 40 10 100 4
2 1 2 3 4 0
3 0 -1 0 0 0
*/

int main(){
    GO_BEYOND;
    ll t=1;
    // cin >> t;
    while(t--) 
        solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50