Submission #1340589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340589		jenterjongle45	Voting Cities (NOI22_votingcity)	C++20	0 / 100	27 ms	2120 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using pii = pair<int,int>;
struct A{
    int u,w,c;
    bool operator<(const A &o)const{
        return w>o.w;
    }
};
int32_t main(){
    int n,m,k;cin>>n>>m>>k;
    vector<int> T(k);
    vector<vector<pii>> adj(n+1);
    for(int &x:T) cin>>x;
    while (m--){
        int u,v,w;cin>>u>>v>>w;
        adj[v].push_back({u,w});
    }
    vector<vector<int>> d(n+1,vector<int> (1<<5));
    priority_queue<A> pq;
    int Q;cin>>Q;
    while(Q--){
        int t;cin>>t;
        vector<int> s(5);
        for(int &x:s){
            cin>>x;
        }
        for(int i=0;i<n;i++) for(int j=0;j<32;j++) d[i][j]=1e9;
        for(int x:T){
            for(int i=0;i<32;i++){
                d[x][i]=0;
                for(int j=0;j<5;j++){
                    if((1<<j)&i){
                        d[x][i]+=s[j];
                        if(s[j]==-1) goto NO;
                    }
                }
                pq.push({x,d[x][i],i});
                NO:;
            }
        }
        while(!pq.empty()){
            auto [u,w,c]=pq.top();pq.pop();
            // cout<<u<<' '<<w<<'\n';
            if(u==t){
                cout<<w<<"\n";
                goto nx;
            }
            if(w!=d[u][c]) continue;
            for(auto x:adj[u]){
                auto [v,ww]=x;
                for(int i=0;i<5;i++){
                    if(((1<<i)&c)&&d[v][(c)^(1<<i)]>w+(ww)-ww*(i+1)/10){
                        d[v][(c)^(1<<i)]=w+(ww)-ww*(i+1)/10;
                        pq.push({v,d[v][(c)^(1<<i)],(c)^(1<<i)});
                    }
                }
                if(d[v][c]>w+ww){
                    d[v][c]=w+ww;
                    // cout<<u<<' '<<v<<'\n';
                    pq.push({v,w+ww,c});
                }
            }
        }
        cout<<-1<<'\n';
        nx:;
        while(!pq.empty()) pq.pop();

        
    
    }
    
}

• 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