Submission #1272119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272119		warrenn	Voting Cities (NOI22_votingcity)	C++20	100 / 100	24 ms	2352 KiB

Main

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

vector<int>city;
vector<pair<int,int> >adj[5002];
int dis[5002][33];

void djikstra(){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> >  >pq;
    for(auto g : city){
        dis[g][0]=0;
        pq.push({0,g});
    }  

    while(!pq.empty()){
        int cur=pq.top().second;
        pq.pop();
       // cout<<cur<<endl;

        for(auto i : adj[cur]){
            int ada=1e15;
            for(int q=0;q<32;q++){
                if(dis[i.first][q]>dis[cur][q]+i.second){
                   // cout<<i.first<<" "<<cur<<endl;
                    dis[i.first][q]=dis[cur][q]+i.second;
                    if(dis[i.first][q]<1e15){
                        ada=min(ada,dis[i.first][q]);
                    }
                }

                for(int w=0;w<5;w++){
                    if((q & (1<<w))==0){
                        int brp=dis[cur][q]+(i.second*(10-w-1)/10);
                        if(dis[i.first][q | (1<<w)]>brp){
                            dis[i.first][q | (1<<w)]=brp;
                            if(brp<1e15){
                                ada=min(ada,brp);
                            }
                        }
                    }
                }
            }
            if(ada!=1e15){
                pq.push({ada,i.first});
            }
        }
    }

}

signed main(){
    int n,e,k;
    cin>>n>>e>>k;
    for(int w=1;w<=k;w++){
        int x;
        cin>>x;
        city.push_back(x);
    }
    for(int t=1;t<=e;t++){
        int u,v,w;
        cin>>u>>v>>w;
        adj[v].push_back({u,w});
    }
    for(int q=0;q<n;q++){
        for(int w=0;w<32;w++){
            dis[q][w]=1e15;
        }
    }
    djikstra();
    int u;
    cin>>u;

    while(u--){
        int s;
        cin>>s;
        int price[5];
        for(int q=0;q<5;q++){
            cin>>price[q];
        }
        int minim=1e15;
        for(int q=0;q<32;q++){
            int harga=dis[s][q];
          //  cout<<harga<<endl;
            for(int w=0;w<5;w++){
                if(((q&(1<<w)))!=0){
                    harga+=price[w];
                    if(price[w]==-1){
                        harga=1e15;
                    }
                }
            }
            minim=min(minim,harga);
          //  cout<<harga<<" "<<q<<endl;
        }
        if(minim==1e15){
            cout<<-1<<endl;
        }
        else{
            cout<<minim<<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