oj.uz

Submission #992101

# Submission time Handle Problem Language Result Execution time Memory
992101 2024-06-03T23:56:58 Z biximo Voting Cities (NOI22_votingcity) C++17
0 / 100
 99 ms 8400 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 8400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 7120 KB Output isn't correct
2 Halted 0 ms 0 KB -