제출 #992101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
992101		biximo	Voting Cities (NOI22_votingcity)	C++17	0 / 100	99 ms	8400 KiB

Main

#include <bits/stdc++.h>
#define N 5005
#define INF 1000000000000000000LL
using namespace std;
typedef long long ll;
typedef array<ll, 2> p2;
typedef tuple<ll, int, int> p3;
int n, m, q, T[N], k, p[6];
vector<p2> adj[N];
ll dist[N][1<<5];
priority_queue<p3> pq;
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= k; i ++) {
    	cin >> T[i];
    }
    while(m --) {
    	int a, b, c;
    	cin >> a >> b >> c;
    	adj[a].push_back({b,c});
    	adj[b].push_back({a,c});
    }
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < (1<<5); j ++) {
			dist[i][j] = INF;
		}
	}
	for(int i = 1; i <= k; i ++) {
		dist[T[i]][0] = 0;
		pq.push({0,T[i],0});
	}
	while(pq.size()) {
		auto[ds,c1,c2] = pq.top(); pq.pop();
		ds = -ds;
		if(dist[c1][c2] != ds) continue;
		for(auto[i,v]: adj[c1]) {
			for(int j = 0; j <= 5; j ++) {
				if(j > 0 && (c2&1<<(j-1))) continue;
				int nc2 = c2|((j>0)?(1<<(j-1)):0);
				int nc1 = i;
				if(dist[nc1][nc2] > ds+v*(10-j)/10) {
					dist[nc1][nc2] = ds+v*(10-j)/10;
					pq.push({-dist[nc1][nc2], nc1, nc2});
				}
			}
		}
	}
    cin >> q;
    while(q--) {
    	int start;
    	cin >> start >> p[1] >> p[2] >> p[3] >> p[4] >> p[5];
    	ll mv = INF;
    	for(int i = 0; i < (1<<5); i ++) {
    		ll cs = dist[start][i];
    		for(int j = 0; j < 5; j ++) {
    			if(~i&1<<j) continue;
    			if(p[j+1] == -1) cs = INF;
    			else cs += p[j+1];
    		}
    		mv = min(mv, cs);
    	}
    	assert(mv >= 0);
    	if(mv == INF) cout << "-1\n";
    	else cout << mv << "\n";
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 10
• Subtask 7: 0 / 15
• Subtask 8: 0 / 50