Submission #1184992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184992		asli_bg	Voting Cities (NOI22_votingcity)	C++20	100 / 100	69 ms	8376 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<bool> vb;

#define fi first
#define se second
#define pb push_back

#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
#define sp <<" "<<

#define DEBUG(x) cout<<(#x) sp x<<endl

const int INF=1e18;
const int MAXN=5e3+5;
const int MAXK=35;

int n,e,k;

vii adj[MAXN];
bool mark[MAXN];

int p[10];
int d[MAXN][MAXK];

void dij(){
    priority_queue<pair<int,pii>> s;

    FORE(i,1,n+1){
        for(int j=0;j<(1<<5);j++){
            d[i][j]=INF;
        }

        if(mark[i]){
            d[i][0]=0;
            s.push({0,{i,0}});
        }
    }

    while(!s.empty()){
        auto el=s.top();
        s.pop();
        
        int dd=-el.fi;
        int nd=el.se.fi;
        int mask=el.se.se;
        
        if(dd>d[nd][mask]) continue;

        for(auto [kom,cost]:adj[nd]){
            //ticket kullanma
            if(d[kom][mask]>d[nd][mask]+cost){
                d[kom][mask]=d[nd][mask]+cost;
                s.push({-d[kom][mask],{kom,mask}});
            }

            //ticket kullan
            for(int bt=0;bt<5;bt++){
                if(mask&(1<<bt)) continue; //zaten kullandıysam ticketi
                if(p[bt+1]==-1) continue; //böyle bir ticket yoksa

                int yeni=mask+(1<<bt);
                int cost2=cost*(10-(bt+1))/10;

                if(d[kom][yeni]>d[nd][mask]+cost2){
                    d[kom][yeni]=d[nd][mask]+cost2;
                    s.push({-d[kom][yeni],{kom,yeni}});
                }
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);


    cin>>n>>e>>k;
    vi tt(k+1);
    FORE(i,1,k+1){
        cin>>tt[i];
        tt[i]++;
        mark[tt[i]]=true;
    }

    FOR(i,e){
        int a,b,c;
        cin>>a>>b>>c;
        a++;b++;
        adj[b].pb({a,c});
    }

    dij();

    int q;
    cin>>q;
    while(q--){
        int s;
        cin>>s>>p[1]>>p[2]>>p[3]>>p[4]>>p[5];

        s++;

        int res=INF;
        for(int mask=0;mask<(1<<5);mask++){
            int ans=d[s][mask];
            for(int bt=0;bt<5;bt++){
                if(mask&(1<<bt)){
                    if(p[bt+1]==-1){
                        ans+=INF;
                    }
                    else{
                        ans+=p[bt+1];
                    }
                }
            }
            res=min(res,ans);
        }

        cout<<(res==INF?-1:res)<<endl;
    }
}

• 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