oj.uz

Submission #522126

# Submission time Handle Problem Language Result Execution time Memory
522126 2022-02-03T21:43:42 Z sidon Cities (BOI16_cities) C++17
100 / 100
 1595 ms 40520 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<int> q;
 
		for(int u = 0; u < N; ++u)
			if(d[u] < INF) q.push(-(d[u] * Z + u));
 
		while(!empty(q)) {
			int dist = (-q.top()) / Z, u = (-q.top()) % Z;
			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) * Z + 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 26828 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 21644 KB Output is correct
2 Correct 382 ms 20896 KB Output is correct
3 Correct 220 ms 15220 KB Output is correct
4 Correct 61 ms 16964 KB Output is correct
5 Correct 222 ms 17612 KB Output is correct
6 Correct 58 ms 13892 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 10 ms 14540 KB Output is correct
2 Correct 12 ms 14540 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14540 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 27956 KB Output is correct
2 Correct 742 ms 27184 KB Output is correct
3 Correct 505 ms 21664 KB Output is correct
4 Correct 472 ms 26700 KB Output is correct
5 Correct 133 ms 23704 KB Output is correct
6 Correct 75 ms 25520 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 40472 KB Output is correct
2 Correct 1595 ms 40520 KB Output is correct
3 Correct 1512 ms 39816 KB Output is correct
4 Correct 1000 ms 34132 KB Output is correct
5 Correct 839 ms 39168 KB Output is correct
6 Correct 204 ms 36308 KB Output is correct
7 Correct 82 ms 38192 KB Output is correct