oj.uz

Submission #522124

# Submission time Handle Problem Language Result Execution time Memory
522124 2022-02-03T21:32:07 Z sidon Cities (BOI16_cities) C++17
100 / 100
 1858 ms 44016 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int Z = 1e5, INF = 1e18;
 
int N, K, M, c[5], dp[32][Z];
vector<array<int, 2>> g[Z];
 
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K >> M;
 
	for(int i = 0; i < K; ++i)
		cin >> c[i], --c[i];
 
	for(int i = 0; i < M; ++i) {
		int u, v, w; cin >> u >> v >> w;
		--u, --v;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
 
	for(int i = 1; i < (1<<K); ++i)
		fill(dp[i], dp[i] + Z, INF);
 
	for(int i = 0; i < K; ++i)
		dp[1<<i][c[i]] = 0;
 
	for(int i = 1; i < (1<<K); ++i) {
		for(int j = 0; j < K; ++j) if(i & (1<<j)) {
			for(int u = 0; u < N; ++u)
				dp[i][u] = min(dp[i][u], dp[i ^ (1<<j)][u] + dp[1<<j][u]);
		}
 
		int *d = dp[i];
		priority_queue<array<int, 2>> q;
 
		for(int u = 0; u < N; ++u)
			if(d[u] < INF) q.push({-d[u], u});
 
		while(!empty(q)) {
			auto [dist, u] = q.top(); q.pop();
			if(dist != -d[u]) continue;
			for(auto &[v, w] : g[u])
				if(d[u] + w < d[v])
					q.push({-(d[v] = d[u] + w), v});
		}
	}
 
	cout << *min_element(dp[(1<<K)-1], dp[(1<<K)-1] + Z);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 7 ms 14412 KB Output is correct
5 Correct 12 ms 26852 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 479 ms 24908 KB Output is correct
2 Correct 436 ms 24280 KB Output is correct
3 Correct 259 ms 17104 KB Output is correct
4 Correct 60 ms 17184 KB Output is correct
5 Correct 233 ms 19496 KB Output is correct
6 Correct 55 ms 14012 KB Output is correct
7 Correct 6 ms 8268 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14560 KB Output is correct
2 Correct 11 ms 14540 KB Output is correct
3 Correct 10 ms 14488 KB Output is correct
4 Correct 9 ms 14476 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 926 ms 31152 KB Output is correct
2 Correct 882 ms 30704 KB Output is correct
3 Correct 561 ms 23276 KB Output is correct
4 Correct 495 ms 28476 KB Output is correct
5 Correct 144 ms 24224 KB Output is correct
6 Correct 72 ms 25548 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1853 ms 44016 KB Output is correct
2 Correct 1858 ms 43736 KB Output is correct
3 Correct 1755 ms 43324 KB Output is correct
4 Correct 1222 ms 36004 KB Output is correct
5 Correct 969 ms 41028 KB Output is correct
6 Correct 227 ms 36820 KB Output is correct
7 Correct 83 ms 38328 KB Output is correct