oj.uz

Submission #391124

# Submission time Handle Problem Language Result Execution time Memory
391124 2021-04-17T22:44:26 Z nikatamliani Cities (BOI16_cities) C++14
100 / 100
 2528 ms 49384 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+10;
const ll oo = 1e18;
ll n, k, m, important[10], dp[32][N];
vector<pair<ll, ll>> edges[N];
void run_dijkstra(int mask) {
	priority_queue<pair<ll, int>> q;
	vector<ll> dist(n);
	vector<bool> visited(n);
	for(int i = 0; i < n; ++i) {
		dist[i] = dp[mask][i];
		q.push({-dist[i], i});
	}
	while(!q.empty()) {
		pair<ll, int> p = q.top(); q.pop();
		if(dist[p.second] < -p.first) continue;
		for(pair<ll, int> to : edges[p.second]) {
			ll dst = to.second - p.first;
			if(dist[to.first] > dst) {
				dist[to.first] = dst;
				q.push({-dst, to.first});
			}
		}
	}
	for(int i = 0; i < n; ++i) {
		dp[mask][i] = dist[i];
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> m;
	for(int i = 0; i < k; ++i) {
		cin >> important[i];
		--important[i];
	}
	for(int i = 0; i < n; ++i) {
		for(int mask = 0; mask < (1 << k); ++mask) {
			dp[mask][i] = oo;
		}
	}
	for(int i = 0; i < k; ++i) {
		dp[1 << i][important[i]] = 0;
	}
	for(int i = 0; i < m; ++i) {
		ll u, v, c;
		cin >> u >> v >> c;
		--u, --v; 
		edges[u].push_back({v, c}); 
		edges[v].push_back({u, c});
	}
	for(int mask = 1; mask < (1 << k); ++mask) {
		for(int i = 0; i < n; ++i) {
			for(int submask = mask; submask > 0; submask = (submask - 1) & mask) {
				dp[mask][i] = min(dp[mask][i], dp[submask][i] + dp[mask ^ submask][i]);
			}
		}
		run_dijkstra(mask);
	}
	ll ans = oo;
	for(int i = 0; i < n; ++i) {
		ans = min(ans, dp[(1 << k) - 1][i]);
	}
	cout << ans << endl;
}

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 4940 KB Output is correct
3 Correct 3 ms 5020 KB Output is correct
4 Correct 3 ms 5068 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 690 ms 30344 KB Output is correct
2 Correct 644 ms 29744 KB Output is correct
3 Correct 397 ms 22204 KB Output is correct
4 Correct 79 ms 15372 KB Output is correct
5 Correct 351 ms 26972 KB Output is correct
6 Correct 87 ms 15208 KB Output is correct
7 Correct 7 ms 5324 KB Output is correct
8 Correct 5 ms 5196 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5420 KB Output is correct
2 Correct 9 ms 5452 KB Output is correct
3 Correct 7 ms 5324 KB Output is correct
4 Correct 7 ms 5296 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1304 ms 36736 KB Output is correct
2 Correct 1258 ms 36044 KB Output is correct
3 Correct 864 ms 28452 KB Output is correct
4 Correct 685 ms 27100 KB Output is correct
5 Correct 190 ms 18084 KB Output is correct
6 Correct 84 ms 17708 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2528 ms 49384 KB Output is correct
2 Correct 2473 ms 49052 KB Output is correct
3 Correct 2510 ms 48836 KB Output is correct
4 Correct 1764 ms 41220 KB Output is correct
5 Correct 1280 ms 33644 KB Output is correct
6 Correct 292 ms 19636 KB Output is correct
7 Correct 98 ms 18076 KB Output is correct