Submission #1166337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166337		NK_	Cities (BOI16_cities)	C++17	100 / 100	2298 ms	42664 KiB

cities

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
template<class T> using pq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using vl = V<ll>;
using vi = V<int>;
using pl = pair<ll, ll>;
using vpl = V<pl>;

const ll INFL = 2e18;

const int kax = 5;
const int nax = 1e5+5;
ll dp[nax][1 << kax];
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K, M; cin >> N >> K >> M;

	for(int i = 0; i < N; i++) for(int j = 0; j < (1 << K); j++) {
	    dp[i][j] = INFL;
	}

	for(int i = 0; i < K; i++) {
		int x; cin >> x; --x;
		dp[x][1 << i] = 0;
	}

	V<vpl> adj(N); for(int i = 0; i < M; i++) {
		int u, v, w; cin >> u >> v >> w; --u, --v;
		adj[u].pb(mp(v, w));
		adj[v].pb(mp(u, w));
	}

	pq<pl> q; 
	for(int m = 1; m < (1 << K); m++) {
	    for(int u = 0; u < N; u++) {
			for(int sub = (m - 1) & m; sub > 0; sub = (sub - 1) & m) {
			  if (sub < (m ^ sub)) break;
				// cout << u << " => " << sub << " " << (m ^ sub);
				// cout << " => " << dp[u][sub] << " " << dp[u][m ^ sub] << endl;
				dp[u][m] = min(dp[u][m], dp[u][sub] + dp[u][m ^ sub]);
			}
			// cout << u << " " << dp[u][m] << endl;
		  }
			
		for(int u = 0; u < N; u++) if (dp[u][m] != INFL) {
		    q.push(mp(dp[u][m], u));
		}

		vi vis(N);
		while(sz(q)) {
			int u = q.top().s; q.pop();
			// cout << u << " " << d << endl;

			if (vis[u]) continue;
			vis[u] = 1;

			for(auto& [v, w] : adj[u]) {
				if (dp[v][m] > dp[u][m] + w) {
					dp[v][m] = dp[u][m] + w;
					q.push(mp(dp[v][m], v));
				}
			}	
		}
	}

	ll ans = INFL;

	for(int u = 0; u < N; u++) ans = min(ans, dp[u][(1 << K) - 1]);

	cout << ans << nl;
	exit(0-0);
}

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