제출 #1249765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1249765		nasjes	Voting Cities (NOI22_votingcity)	C++20	100 / 100	158 ms	54348 KiB

Main

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <string>
#include <cstring>
#include <iterator>
#include <random>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
const ll dim = 2*(1e6)+7;
//const ll mod = 1e9 + 7;
const ll inf = 1e17 + 77;
//#define endl "\n"
#define fi first
#define pb push_back
#define se second
#define vll vector<ll>

ll n, m, k;
ll t;
vector<pll>  a[dim];
ll vote[dim];
ll dst[dim][40], vis[dim][40];
ll check(ll mask, vll &b){
    ll fl=0;
    ll cnt=0;
    for(int i=0; i<5; i++){
        ll cur=(mask)&(1ll<<i);
        if(cur!=0 && b[i]==-1)cnt=inf;
        else if(cur!=0)cnt+=b[i];
    }
    return cnt;
}
int main() {

    ll  u, w,q,   v, y;
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   // cin>>t;
   t=1;
    while(t--) {
        cin >> n>>m>>k;
        for(int i=0; i<=n; i++){
            for(int j=0; j<=33; j++){
                dst[i][j]=inf;
                vis[i][j]=0;
            }
        }
        for(int i=1; i<=k; i++){
            cin>>vote[i];
            vote[i]++;
        }
        for(int i=1; i<=m; i++){
            cin>>u>>v>>w;
            u++;
            v++;
            a[v].pb({u, w});
        }
        set<pair<ll, pll>> s;
        for(int i=1; i<=k; i++){
            dst[vote[i]][0]=0;
            s.insert({0, {vote[i], 0}});
        }
        while(s.size()>0){
            ll v=(*s.begin()).se.fi;
            ll pw=(*s.begin()).se.se;
           // cout<<(*s.begin()).fi<<" "<<v<<" "<<pw<<endl;
            s.erase(s.begin());
            if(vis[v][pw])continue;
            vis[v][pw]=1;
            for(auto x:a[v]){
                ll to=x.fi;
                w=x.se;
                for(ll i=0; i<5; i++){
                    if((1ll<<i)&pw)continue;
                    ll w1=(w/10)*(10-i-1);
                    ll mask=(pw|(1ll<<i));
                    if(dst[to][mask]<dst[v][pw]+w1)continue;
                    s.erase({dst[to][mask], {to, mask}});
                    dst[to][mask]=dst[v][pw]+w1;
                    s.insert({dst[to][mask], {to, mask}});

                }
                if(dst[to][pw]<dst[v][pw]+w)continue;
                s.erase({dst[to][pw], {to, pw}});
                dst[to][pw]=dst[v][pw]+w;
                s.insert({dst[to][pw], {to, pw}});
            }
        }
        cin>>q;
        while(q--){
            ll st;
            vll b(5);
            cin>>st>>b[0]>>b[1]>>b[2]>>b[3]>>b[4];
            st++;
            ll ans=inf;
            for(ll i=0; i<32; i++){
                ll price=(check(i, b));
                ans=min(dst[st][i]+price, ans);
            }
            if(ans>=inf)cout<<-1<<endl;
            else cout<<ans<<endl;
        }


    }
    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