Submission #1273589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273589		ahmd_ibraaa	Voting Cities (NOI22_votingcity)	C++20	100 / 100	62 ms	5268 KiB

Main

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

#define int long long
#define fi first
#define sec second

signed main(){
	int N,E,K;
	cin>>N>>E>>K;
	int vc[K+1];
	int dis[N+1][32];
	vector<pair<int,int>> adj[N+1];
	for(int i=1; i<=K; i++){
		cin>>vc[i];
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<=31; j++){
			dis[i][j] = 1e18;
		}
	}
	
	for(int i=1; i<=E; i++){
		int u,v,c;
		cin>>u>>v>>c;
		adj[v].push_back({u,c});
	}
	priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> pq;
	for(int i=1; i<=K; i++){
		dis[vc[i]][0] = 0;
		pq.push({0, {vc[i], 0}});
		for(int j=0; j<32; j++) dis[vc[i]][j] = 0;
	}
	
	while(!pq.empty()){
		auto now = pq.top();
		pq.pop();
		if(now.fi > dis[now.sec.fi][now.sec.sec]) continue;
		for(auto itr:adj[now.sec.fi]){
			if(dis[itr.fi][now.sec.sec]>(now.fi+itr.sec)){
				dis[itr.fi][now.sec.sec] = now.fi+itr.sec;
				pq.push({dis[itr.fi][now.sec.sec], {itr.fi, now.sec.sec}});
			}
			
			for(int i=0; i<5; i++){
				if((now.sec.sec & (1<<i))!=0) continue;
				int disNext = now.fi + itr.sec*(10 - i - 1)/10;
				int maskNext = now.sec.sec | (1<<i);
				if(dis[itr.fi][maskNext] > disNext){
					dis[itr.fi][maskNext] = disNext;
					pq.push({disNext, {itr.fi, maskNext}});
				}
			}
		}
	}
	
	int Q; cin>>Q;
	while(Q--){
		int s, p[5];
		cin>>s;
		int ptotal = 0;
		for(int i=0; i<5; i++){
			cin>>p[i];
			if(p[i]!=-1) ptotal|=(1<<i);
		}
		int ans = 1e18;
		for(int m=0; m<32; m++){
			int curAns = dis[s][m];
			if(dis[s][m]!=1e18 && (ptotal&m)==m){
				for(int i=0; i<5; i++){
					if((m & (1<<i))) curAns += p[i];
				}
				ans = min(ans, curAns);
			}
		}
		if(ans>=1e18) cout<<-1<<endl;
		else cout<<ans<<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