제출 #1272389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1272389		choed	Voting Cities (NOI22_votingcity)	C++20	0 / 100	4 ms	1128 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=2000;
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));
vector<ll> sum(MAXN+1, 0LL);
multiset<ll> ms[MAXN+1]; // bilangan terbesar saat costnya min
vector<ll> disc; // diskon yang tersedia

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

    // cout << u << ' ' << c << ' ' << mask << " CURRENT" << endl;
    
    ll tot, idx=0, BIT=__popcount(mask);
    for(auto x: edge[u]){
        tot=sum[u];
        ms[u].insert(x.se);
        idx=0;
        // cout << x.fi << ' ' << x.se << " EDGE" << endl;
        // cout << tot << " SUM" << endl;

        // cout << "HARGA ROAD" << endl;
        for(auto it=ms[u].rbegin(); it!=ms[u].rend(); it++){
            ll y = *it;
            // cout << y << ' ';
            if(idx<disc.size()){
                // cout << disc[idx];
                tot+=(y*disc[idx])/10;
                idx++;
            }else tot+=y;
            // cout << endl;
        }

        // cout << tot << " TOTAL" << endl;
        if(tot<mn[x.fi][mask]){
            mn[x.fi][mask]=tot;
            ms[x.fi]=ms[u];
            sum[x.fi]=sum[u];
            if(ms[x.fi].size()>BIT){
                sum[x.fi]+=*ms[x.fi].begin();
                ms[x.fi].erase(ms[x.fi].begin());
            }
            pq.push({tot, {x.fi, mask}});
        }

        ms[u].erase(ms[u].find(x.se));
    }
}

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});
        edge[v].push_back({u,c});
    }

    for(int i=0; i<MAXB; i++){
        for(int j=4; j>=0; j--){
            if((i&(1LL<<j))>0)
                disc.push_back(10-(j+1));
        }

        for(int j=0; j<k; j++){
            pq.push({0, {t[j], 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);
        }

        while(!pq.empty())
            pq.pop();
        disc.clear();
        for(int i=0; i<=n; i++){
            sum[i]=0;
            ms[i].clear();
        }
    }

    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