oj.uz

Submission #968856

# Submission time Handle Problem Language Result Execution time Memory
968856 2024-04-24T07:48:41 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 1834 ms 117520 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;
	memset(dist, 0x3f, sizeof dist);
	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);
	}
	int max_mask = (1 << k) - 1;
	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 37 ms 102896 KB Output is correct
2 Correct 23 ms 103004 KB Output is correct
3 Correct 23 ms 103004 KB Output is correct
4 Correct 22 ms 102740 KB Output is correct
5 Correct 22 ms 103004 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 117444 KB Output is correct
2 Correct 387 ms 116464 KB Output is correct
3 Correct 297 ms 110280 KB Output is correct
4 Correct 81 ms 111956 KB Output is correct
5 Correct 256 ms 117520 KB Output is correct
6 Correct 75 ms 111816 KB Output is correct
7 Correct 27 ms 103136 KB Output is correct
8 Correct 24 ms 103004 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 103004 KB Output is correct
2 Correct 26 ms 103072 KB Output is correct
3 Correct 25 ms 102992 KB Output is correct
4 Correct 26 ms 102996 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 797 ms 117372 KB Output is correct
2 Correct 772 ms 116652 KB Output is correct
3 Correct 451 ms 110276 KB Output is correct
4 Correct 419 ms 115652 KB Output is correct
5 Correct 150 ms 113076 KB Output is correct
6 Correct 91 ms 114000 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 117368 KB Output is correct
2 Correct 1834 ms 117452 KB Output is correct
3 Correct 1455 ms 116408 KB Output is correct
4 Correct 948 ms 110280 KB Output is correct
5 Correct 776 ms 115664 KB Output is correct
6 Correct 215 ms 113284 KB Output is correct
7 Correct 111 ms 114512 KB Output is correct