Submission #937224

#	Time	Username	Problem	Language	Result	Execution time	Memory
937224		Litusiano	Voting Cities (NOI22_votingcity)	C++17	100 / 100	245 ms	3380 KiB

Main

// #pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#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(t > cost) continue;
				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:20:14: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     if(i > 0 && msk & (1<<(i-1)) || ct[i] == -1) {
      |        ~~~~~~^~~~~~~~~~~~~~~~~~~

• 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