Submission #1272556

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272556		djsksbrbf	Voting Cities (NOI22_votingcity)	C++20	100 / 100	73 ms	8352 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair <int, int> pii;
typedef pair <int, pii> ipi;
#define fi first
#define se second
#define pb push_back
const int MOD = 1e9 + 7;
const int MAX = 3e5 + 5;
const ll INF = 1e15;
#pragma GCC optimize ("Ofast")
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, e, k; cin >> n >> e >> k;
	vector <int> votes;
	vector <pii> adj[n];
	
	for(int i = 0 ; i < k ; i++){
		int x; cin >> x;
		votes.pb(x);
	}
	for(int i = 0 ; i < e ; i++){
		int u, v, w; cin >> u >> v >> w;
		adj[v].pb({u, w});
	}
	
	ll dist[n + 5][(1ll << 5)];
	for(int i = 0 ; i < n + 5 ; i++){
		for(int j = 0 ; j < (1ll << 5) ; j++){
			dist[i][j] = (ll)1e18;
		}
	}
	priority_queue <tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
	for(auto it : votes){
		dist[it][0] = 0;
		q.push({0, it, 0});
	}
	
	while(q.size()){
		auto [dis, cur, mask] = q.top();q.pop();
		if(dist[cur][mask] < dis)continue;
		
		for(auto [nxt, ad] : adj[cur]){
			if(dist[nxt][mask] > dis + ad){
				dist[nxt][mask] = dis + ad;
				q.push({dis + ad, nxt, mask});
			}
			
			for(int i = 0 ; i < 5 ; i++){
				if(!((mask >> i) & 1)){
					int newad = ad;
					newad /= 10;
					newad *= (10 - i - 1);
					
					if(dist[nxt][mask | (1ll << i)] > dis + newad){
						dist[nxt][mask | (1ll << i)] = dis + newad;
						q.push({dis + newad, nxt, (mask | (1ll << i))});
					}
				}
			}
		}
	}
	
	int qe; cin >> qe;
	while(qe--){
		int st; cin >> st;
		int pay[5];
		for(int i = 0 ; i <5 ; i++)cin >> pay[i];
		
		ll ans = (ll)1e18;
		for(int i = 0 ; i < (1ll << 5) ; i++){
			bool can = 1;
			ll cur = dist[st][i];
			for(int j = 0 ; j < 5 ; j++){
				if((i >> j) & 1){
					if(pay[j] == -1)can = 0;
					else cur += pay[j];
				}
			}
			if(can)ans = min(ans,cur);
		}
		cout << (ans == (ll)1e18 ? -1 : ans) << endl;
	}
	
	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