oj.uz

Submission #968862

# Submission time Handle Problem Language Result Execution time Memory
968862 2024-04-24T07:55:25 Z Hydrolyzed Cities (BOI16_cities) C++14
100 / 100
 1675 ms 46352 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MxK = 7;
const int MxN = 100010;

struct state_t {
	int v;
	ll w;
	bool operator < (const state_t &o) const {
		return w > o.w;
	}
	state_t(int _v, ll _w):
		v(_v), w(_w) {}
};

int a[MxK];
vector<pair<int, ll>> adj[MxN];
ll dist[1 << MxK][MxN], w;
priority_queue<state_t> pq;

signed main(int argc, char *argv[]) {
	cin.tie(nullptr)->ios::sync_with_stdio(false);
	int n, m, k;
	cin >> n >> k >> m;
	int max_mask = (1 << k) - 1;
	for(int mask=0; mask<=max_mask; ++mask) {
		for(int i=1; i<=n; ++i) {
			dist[mask][i] = 1e18 + 100ll;
		}
	}
	for(int i=0; i<k; ++i) {
		cin >> a[i];
		dist[1 << i][a[i]] = 0;
	}
	for(int i=1, u, v; i<=m; ++i) {
		cin >> u >> v >> w;
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	for(int mask=1; mask<=max_mask; ++mask) {
		for(int i=0; i<k; ++i) {
			int this_mask = (1 << i);
			if(!(mask & this_mask)) {
				continue;
			}
			int without_this = (mask ^ this_mask);
			for(int t=1; t<=n; ++t) {
				dist[mask][t] = min(dist[mask][t], dist[this_mask][t] + dist[without_this][t]);
			}
		}
		for(int i=1; i<=n; ++i) {
			pq.emplace(i, dist[mask][i]);
		}
		while(!pq.empty()) {
			state_t now = pq.top(); pq.pop();
			for(auto x: adj[now.v]) {
				ll nxt = x.second + now.w;
				if(dist[mask][x.first] > nxt) {
					pq.emplace(x.first, dist[mask][x.first] = nxt);
				}
			}
		}
	}
	cout << *min_element(dist[max_mask] + 1, dist[max_mask] + n + 1) << "\n";
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 3 ms 10332 KB Output is correct
4 Correct 3 ms 16476 KB Output is correct
5 Correct 6 ms 28760 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 26656 KB Output is correct
2 Correct 417 ms 25824 KB Output is correct
3 Correct 200 ms 17936 KB Output is correct
4 Correct 56 ms 19540 KB Output is correct
5 Correct 228 ms 24264 KB Output is correct
6 Correct 52 ms 17384 KB Output is correct
7 Correct 4 ms 10588 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 5 ms 16732 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 34248 KB Output is correct
2 Correct 724 ms 33736 KB Output is correct
3 Correct 420 ms 26320 KB Output is correct
4 Correct 413 ms 29528 KB Output is correct
5 Correct 136 ms 26800 KB Output is correct
6 Correct 69 ms 27728 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1675 ms 46184 KB Output is correct
2 Correct 1657 ms 46352 KB Output is correct
3 Correct 1576 ms 46144 KB Output is correct
4 Correct 873 ms 38596 KB Output is correct
5 Correct 794 ms 41668 KB Output is correct
6 Correct 195 ms 39088 KB Output is correct
7 Correct 88 ms 40272 KB Output is correct