Submission #1188942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188942		g4yuhg	Cities (BOI16_cities)	C++20	14 / 100	6093 ms	143032 KiB

cities

#include<bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll,ll>
#define N 200005
#define LOG 19
#define inf 1e18
using namespace std;
ll onbit(ll mask, ll i) {
	return mask | (1 << i);
}
ll getbit(ll mask, ll i) {
	return (mask >> i) & 1;
}
ll n, k, m, d[5][N];
ll d2[(1 << 5)][N];
ll ip[5];
vector<pii> adj[N];
void dij() {
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < k; j ++) {
			d[j][i] = inf;
		}
	}
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
	for (int i = 0; i < k; i ++) {
		d[i][ip[i]] = 0;
		pq.push({0, {i, ip[i]}});
	}
	while (pq.size()) {
		auto c = pq.top().fi;
		auto u = pq.top().se;
		//if (u.fi == 2) cout << c << " " << u.fi << " " << u.se << endl;
		pq.pop();
		if (c > d[u.fi][u.se]) continue;
		for (auto v : adj[u.se]) {
			if (d[u.fi][v.fi] > c + v.se) {
				d[u.fi][v.fi] = c + v.se;
				pq.push({d[u.fi][v.fi], {u.fi, v.fi}});
			}
		}
	}
}
void dij2() {
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j < (1 << k); j ++) {
			d2[j][i] = inf;
		}
	}
	priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
	for (int i = 1; i <= n; i ++) {
		for (int mask = 1; mask < (1 << k); mask ++) {
			d2[mask][i] = 0;
			for (int j = 0; j < k; j ++) {
				if (getbit(mask, j) == 1) {
					d2[mask][i] += d[j][i];
				}
			}
			pq.push({d2[mask][i], {mask, i}});
		}
	}
	while (pq.size()) {
		auto c = pq.top().fi;
		auto u = pq.top().se;
		pq.pop();
		if (c > d2[u.fi][u.se]) continue;
		for (auto v : adj[u.se]) {
			ll newc = c + v.se;
			for (int mask = 0; mask < (1 << k); mask ++) {
				if ((mask & u.fi) > 0) continue;
				if (d2[mask | u.fi][v.fi] > newc + d2[mask][v.fi]) {
					d2[mask | u.fi][v.fi] = newc + d2[mask][v.fi];
					pq.push({d2[mask][v.fi], {(mask | u.fi), v.fi}});
				}
			}
		}
	}
}
signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	for (int i = 0; i < k; i ++) {
		cin >> ip[i];
	}
	for (int i = 1; i <= m; i ++) {
		ll u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	dij();
	dij2();
	ll ans = inf;
	//cout << endl;
	for (int i = 1; i <= n; i ++) {
		ans = min(ans, d2[(1 << k) - 1][i]);
		//cout << i << " " << d2[(1 << k) - 1][i] << endl;
		ll sum = 0;
		for (int j = 0; j < k; j ++) {
			sum += d[j][i];
			//cout << j << " " << i << " " << d[j][i] << endl;
		}
		///cout << i << " " << sum << endl;
	}
	cout << ans;
	return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 14 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26