Submission #391124

#	Time	Username	Problem	Language	Result	Execution time	Memory
391124		nikatamliani	Cities (BOI16_cities)	C++14	100 / 100	2528 ms	49384 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26