Submission #1272203

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272203		coderpemula	Voting Cities (NOI22_votingcity)	C++20	100 / 100	80 ms	8396 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
using namespace std;
vector<pii>v[5000];
priority_queue<pair<pii,int>,vector<pair<pii,int>>,greater<pair<pii,int>>>pq;
int jarak[5000][32];
// 2^4
// 11111
signed main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,m,k,t,i,j,c,anu[5],s;
	cin>>n>>m>>k;
	for(i=0;i<n;i++){
		for(j=0;j<32;j++) jarak[i][j] = 1e18;
	}
	for(i=1;i<=k;i++){
		cin>>j;
		pq.push({{0,0},j});
		jarak[j][0] = 0;
	}
	for(i=1;i<=m;i++){
		cin>>j>>t>>c;
		v[t].pb({j,c});
	}
	while(!pq.empty()){
		int node = pq.top().se, st = pq.top().fi.se, jar = pq.top().fi.fi;
		pq.pop();
		//cout<<node<<" "<<st<<" "<<jar<<endl;
		if(jarak[node][st] != jar) continue;
		for(auto x:v[node]){
			if(jarak[x.fi][st] > jar+x.se){
				jarak[x.fi][st] = jar+x.se;
				pq.push({{jarak[x.fi][st],st},x.fi});
			}
			for(i=0;i<5;i++){
				if(!(st&(1<<i))){
					int cost = x.se - x.se/10*(i+1), now = (st|(1<<i));
					if(jarak[x.fi][now] > jar+cost){
						jarak[x.fi][now] = jar+cost;
						pq.push({{jarak[x.fi][now],now},x.fi});
					}
				}
			}
		}
	}
	//cout<<jarak[4][16]<<endl;
	cin>>t;
	while(t--){
		cin>>s;
		for(i=0;i<5;i++) cin>>anu[i];
		int ans = 1e18;
		for(i=0;i<32;i++){
			if(jarak[s][i] == 1e18) continue;
			int temp = 0;
			for(j=0;j<5;j++){
				if(i&(1<<j)){
					if(anu[j] == -1){
						temp = -1;
						break;
					}
					temp += anu[j];
				}
			}
//			cout<<i<<" "<<jarak[s][i]<<endl;
			if(temp != -1) ans = min(ans,jarak[s][i]+temp);
		}
		if(ans == 1e18) ans = -1;
		cout<<ans<<"\n";
	}
	
	return 0;
}

• 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