oj.uz

답안 #942176

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942176 2024-03-10T10:31:54 Z vjudge1 Voting Cities (NOI22_votingcity) C++17
15 / 100
 57 ms 4068 KB 
#include <bits/stdc++.h>

using namespace std;

int 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.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 36 ms 2648 KB Output is correct
7 Correct 14 ms 1884 KB Output is correct
8 Correct 35 ms 2540 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 36 ms 2648 KB Output is correct
7 Correct 14 ms 1884 KB Output is correct
8 Correct 35 ms 2540 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 55 ms 4068 KB Output is correct
12 Correct 16 ms 1884 KB Output is correct
13 Correct 42 ms 2516 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 3 ms 1884 KB Output is correct
7 Incorrect 14 ms 1884 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 36 ms 2648 KB Output is correct
7 Correct 14 ms 1884 KB Output is correct
8 Correct 35 ms 2540 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 3 ms 1884 KB Output is correct
12 Incorrect 14 ms 1884 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 57 ms 3048 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 2536 KB Output is correct
2 Correct 14 ms 1884 KB Output is correct
3 Correct 37 ms 2580 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 36 ms 2648 KB Output is correct
7 Correct 14 ms 1884 KB Output is correct
8 Correct 35 ms 2540 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 55 ms 4068 KB Output is correct
12 Correct 16 ms 1884 KB Output is correct
13 Correct 42 ms 2516 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 3 ms 1884 KB Output is correct
17 Incorrect 14 ms 1884 KB Output isn't correct
18 Halted 0 ms 0 KB -