Submission #966592

#	Time	Username	Problem	Language	Result	Execution time	Memory
966592		Trisanu_Das	Voting Cities (NOI22_votingcity)	C++17	100 / 100	73 ms	10456 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int N, E, K; cin >> N >> E >> K;
	vector<int> T(K);
	for(auto &i : T) cin >> i;
	vector<vector<pair<int, int>>> adj(N);
	for(int i = 0; i < E; i++){
		int u, v, c; cin >> u >> v >> c;
		adj[v].push_back({u, c});
	}
	vector<vector<long long>> dist(32, vector<long long>(N, 1e18));
	vector<vector<bool>> vis(32, vector<bool>(N, false));
	priority_queue<tuple<long long, int, int>> q;
	for(int i = 0; i < K; i++){
		dist[0][T[i]] = 0;
		q.push({0, 0, T[i]});
	}
	while(!q.empty()){
		int mask = get<1>(q.top()); int x = get<2>(q.top()); q.pop();
		if(vis[mask][x]) continue;
		vis[mask][x] = true;
		for(pair<int, int> p : adj[x]){
			int node = p.first; int c = p.second;
			if(dist[mask][node] > dist[mask][x] + c){
				dist[mask][node] = dist[mask][x] + c;
				q.push({-dist[mask][node], mask, node});
			}
			for(int b = 0; b < 5; b++){
				if(!((1 << b) & mask)){
					int nmask = mask + (1 << b);
					long long w = (c * (9 - b)) / 10;
					if(dist[nmask][node] > dist[mask][x] + w){
						dist[nmask][node] = dist[mask][x] + w;
						q.push({-dist[nmask][node], nmask, node});
					}
				}
			}
		}
	}
	int Q; cin >> Q;
	while(Q--){
		int S; cin >> S;
		vector<int> P(5);
		for(auto &i : P) cin >> i;
		long long ans = 1e18;
		for(int i = 0; i < 32; i++){
			long long cost = dist[i][S];
			for(int b = 0; b < 5; b++){
				if((1 << b) & i){
					if(P[b] == -1) cost = 1e18;
					else cost += P[b];
				}
			}
			ans = min(ans, cost);
		}
		if(ans == 1e18) cout << -1 << "\n";
		else cout << ans << "\n";
	}
}

• 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