oj.uz

Submission #361264

# Submission time Handle Problem Language Result Execution time Memory
361264 2021-01-29T02:25:38 Z hoaphat1 Cities (BOI16_cities) C++17
100 / 100
 5861 ms 108348 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,m;
  cin >> n >> k >> m;
  vector<int> a(k);
  for (int i = 0; i < k; i++) {
		cin >> a[i];
	}
	vector<vector<pair<int,int>>> g(n + 1);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	const long long inf = 1e18;
  vector<vector<long long>> d(n + 1, vector<long long> (1 << k, inf));
  priority_queue<tuple<long long, int, int>> pq;
  for (int i = 0; i < k; i++) {
  	d[a[i]][1 << i] = 0;
  	pq.emplace(0, a[i], 1 << i);
	}
	for (int i = 1; i <= n; i++) {
		d[i][0] = 0;
		pq.emplace(0, i, 0);
	}
	while (!pq.empty()) {
		auto x = pq.top();pq.pop();
		if (-get<0>(x) != d[get<1>(x)][get<2>(x)]) continue;
		int v = get<1>(x);
		int mask = get<2>(x);
		if (mask == (1 << k) - 1) return cout << -get<0>(x), 0;
		for (int i = 0; i < k; i++) {
			if (mask >> i & 1) continue;
			if (d[v][mask] + d[v][1 << i] < d[v][mask | (1 << i)]) {
				d[v][mask | (1 << i)] = d[v][mask] + d[v][1 << i];
				pq.emplace(-d[v][mask | (1 << i)], v, mask | (1 << i));
			}
		}
		for (auto& x : g[v]) {
			int u = x.first;
			if (d[u][mask] > d[v][mask] + x.second) {
				d[u][mask] = d[v][mask] + x.second;
				pq.emplace(-d[u][mask], u, mask);
			}
		}
	}
	assert(false);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 27644 KB Output is correct
2 Correct 764 ms 27088 KB Output is correct
3 Correct 197 ms 18152 KB Output is correct
4 Correct 72 ms 5492 KB Output is correct
5 Correct 351 ms 20188 KB Output is correct
6 Correct 62 ms 5228 KB Output is correct
7 Correct 3 ms 748 KB Output is correct
8 Correct 2 ms 492 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1004 KB Output is correct
2 Correct 6 ms 1004 KB Output is correct
3 Correct 4 ms 620 KB Output is correct
4 Correct 4 ms 748 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2518 ms 58520 KB Output is correct
2 Correct 2054 ms 57920 KB Output is correct
3 Correct 1275 ms 39120 KB Output is correct
4 Correct 1270 ms 32024 KB Output is correct
5 Correct 201 ms 15072 KB Output is correct
6 Correct 80 ms 7284 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5826 ms 103780 KB Output is correct
2 Correct 5861 ms 108348 KB Output is correct
3 Correct 5380 ms 107624 KB Output is correct
4 Correct 2637 ms 70004 KB Output is correct
5 Correct 3256 ms 59196 KB Output is correct
6 Correct 566 ms 20632 KB Output is correct
7 Correct 116 ms 11256 KB Output is correct