Submission #937221

#TimeUsernameProblemLanguageResultExecution timeMemory
937221LitusianoVoting Cities (NOI22_votingcity)C++17
45 / 100
1064 ms7704 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int inf = 1e18; vector<vector<pair<int,int>>> G; vector<vector<int>> dp; vector<int> ct; void dijkstra(int s){ priority_queue<tuple<int,int,int>>pq; pq.push({0,s,0}); // cost node msk while(!pq.empty()){ int w,u,msk; tie(w,u,msk) = pq.top(); pq.pop(); if(w > dp[u][msk]) continue; for(auto p : G[u]){ int v = p.first; int cost = p.second; for(int i = 0; i<6; i++){ if(i > 0 && msk & (1<<(i-1)) || ct[i] == -1) { continue; } int t = cost-(i*(cost/10)) + ct[i]; if(!i){ if(dp[v][msk] > dp[u][msk] + t){ dp[v][msk] = dp[u][msk]+t; pq.push({-dp[v][msk],v,msk}); } } else{ if(dp[v][msk ^ (1<<(i-1))] > dp[u][msk] + t){ dp[v][msk ^ (1<<(i-1))] = dp[u][msk]+t; pq.push({-dp[u][msk]-t, v,(msk ^ (1<<(i-1))) }); } } } } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,e,k; cin>>n>>e>>k; vector<int> good; for(int i = 0; i<k; i++){ int x; cin>>x; good.push_back(x); } G.resize(n+1); for(int i = 0; i<e; i++){ int u,v,w; cin>>u>>v>>w; G[u].push_back({v,w}); } int q; cin>>q; while(q--){ ct.assign(6,0); dp.assign(n+1, vector<int>(32, inf)); int s; cin>>s; // cerr<<"S: "<<s<<endl; for(int i = 1; i<=5; i++) cin>>ct[i]; dp[s][0] = 0; dijkstra(s); int ans = inf; for(int i = 0; i<k; i++){ // cerr<<good[i]<<endl; for(int j = 0; j<32; j++){ ans = min(ans,dp[good[i]][j]); } } if(ans == inf) ans = -1; cout<<ans<<"\n"; } }

Compilation message (stderr)

Main.cpp: In function 'void dijkstra(long long int)':
Main.cpp:18:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   18 |     if(i > 0 && msk & (1<<(i-1)) || ct[i] == -1) {
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...