Submission #1272385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272385		burnthememory	Voting Cities (NOI22_votingcity)	C++20	100 / 100	71 ms	8732 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define fi first
#define se second
 
const ll N = 5000+10;
vector<vector<ll>> dis(N, vector<ll> ((1<<5), 1e18));
vector<vector<pair<ll, ll>>> adj(N);

void solve() {
	ll n, e, k; cin >> n >> e >> k;
	ll t[n]; 
	
	for(int i = 0; i < k; i++){
		cin >> t[i];
		adj[n].pb(mp(t[i], 0));
	}
	dis[n][0] = 0;
	
	for(int i = 0; i < e; i++){
		ll u, v, w; cin >> u >> v >> w;
		adj[v].pb(mp(u, w));
	}
	
	priority_queue<pair<ll, pair<ll, ll>>> pq;
	pq.push(mp(0, mp(n, 0)));
	while(!pq.empty()){
		auto cur = pq.top();
		ll u = cur.se.fi, id = cur.se.se, diz = cur.fi*-1;
		pq.pop();
		if(diz > dis[u][id]){
			continue;
		}
//		cout << u << " " << id << " " << diz << endl;
		
		for(auto next : adj[u]){
			ll v = next.fi, len = next.se;
			ll newd = diz + len;
			if(newd < dis[v][ id ]){
				dis[v][id] = newd;
				pq.push(mp(newd*-1, mp(v, id) )); 
			}
			
			if(u==n) continue;
			
			for(int bit = 0; bit < 5; bit ++){
				if(id & (1<<bit)) continue;
				ll newdis = diz + len-((len * (bit+1))/10);
				
				if(newdis < dis[v][ (id^(1<<bit)) ]){
					dis[v][ (id^(1<<bit)) ] = newdis;
					pq.push(mp(newdis*-1, mp(v, (id^(1<<bit))) )); 
				}
				
				
//			cout <<  " " << v << " " << (id^(1<<bit)) << " " << len << " " << ((len * (bit+1))/10) << endl;
			}
		}
	}
	
	
	ll query; cin >> query;
	while(query--){
		ll u; cin >> u;
		ll p[5]; 
		for(int i = 0; i < 5;  i++) cin >> p[i];
		
		ll ans = 1e18;
		for(int j = 0; j < (1<<5); j ++){
			ll ok = 1, cur = dis[u][j];
			for(int bit = 0; bit < 5; bit++){
				if(!(j & (1 << bit))) continue; 
				if(p[bit] == -1) ok = 0;
				cur += p[bit];
			}
			if(!ok) continue; 
			ans = min(ans, cur);
//			cout << " " << ans << " " << cur << " " << j << endl;
		}
		
		cout << (ans == 1e18 ? -1 : ans) << endl;
		
		
	}
	
	
	
	
	
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll t=1; 
//  cin >> t;
  while(t--) solve();
}

//

• 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