oj.uz

Submission #522122

# Submission time Handle Problem Language Result Execution time Memory
522122 2022-02-03T21:31:09 Z sidon Cities (BOI16_cities) C++17
100 / 100
 2355 ms 47908 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
using T = array<int, 2>;
 
const int Z = 1e5, INF = 1e18;
 
int N, K, M, c[5], dp[32][Z];
 
vector<T> g[Z];
 
struct comp {
	bool operator()(const T &i, const T &j) {
		return i[0] < j[0];
	}
};
 
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<T, vector<T>, comp> 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 3 ms 4940 KB Output is correct
2 Correct 3 ms 4976 KB Output is correct
3 Correct 4 ms 8048 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 483 ms 29008 KB Output is correct
2 Correct 461 ms 28556 KB Output is correct
3 Correct 243 ms 19100 KB Output is correct
4 Correct 62 ms 20624 KB Output is correct
5 Correct 268 ms 24000 KB Output is correct
6 Correct 66 ms 17404 KB Output is correct
7 Correct 6 ms 8268 KB Output is correct
8 Correct 6 ms 5116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14592 KB Output is correct
2 Correct 11 ms 14528 KB Output is correct
3 Correct 9 ms 14440 KB Output is correct
4 Correct 9 ms 14496 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 35548 KB Output is correct
2 Correct 922 ms 34820 KB Output is correct
3 Correct 604 ms 25396 KB Output is correct
4 Correct 594 ms 32644 KB Output is correct
5 Correct 164 ms 28068 KB Output is correct
6 Correct 72 ms 28976 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2140 ms 47908 KB Output is correct
2 Correct 2355 ms 47868 KB Output is correct
3 Correct 2070 ms 47508 KB Output is correct
4 Correct 1397 ms 38012 KB Output is correct
5 Correct 1041 ms 45060 KB Output is correct
6 Correct 240 ms 40688 KB Output is correct
7 Correct 110 ms 41768 KB Output is correct