oj.uz

Submission #911538

# Submission time Handle Problem Language Result Execution time Memory
911538 2024-01-19T03:23:40 Z NK_ Cities (BOI16_cities) C++17
100 / 100
 5713 ms 51652 KB 
// 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;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, K, M; cin >> N >> K >> M;

	V<vl> dp(N, vl(1 << K, 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 t = 0; t < 2; t++) {
			for(int u = 0; u < N; u++) q.push(mp(dp[u][m], u));

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

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

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

			// cout << m << endl;
			for(int u = 0; u < N; u++) {
				for(int sub = m; sub > 0; sub = (sub - 1) & m) {
					// 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;
			}
			// cout << endl;
		}
	}

	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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 27996 KB Output is correct
2 Correct 1129 ms 27972 KB Output is correct
3 Correct 798 ms 20168 KB Output is correct
4 Correct 54 ms 9552 KB Output is correct
5 Correct 496 ms 24516 KB Output is correct
6 Correct 48 ms 9556 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 600 KB Output is correct
2 Correct 6 ms 844 KB Output is correct
3 Correct 4 ms 720 KB Output is correct
4 Correct 3 ms 604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2457 ms 34240 KB Output is correct
2 Correct 2583 ms 38968 KB Output is correct
3 Correct 1884 ms 28624 KB Output is correct
4 Correct 1375 ms 26648 KB Output is correct
5 Correct 208 ms 16248 KB Output is correct
6 Correct 73 ms 15460 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5689 ms 47556 KB Output is correct
2 Correct 5713 ms 51652 KB Output is correct
3 Correct 5269 ms 50780 KB Output is correct
4 Correct 4040 ms 41164 KB Output is correct
5 Correct 2126 ms 32972 KB Output is correct
6 Correct 357 ms 17448 KB Output is correct
7 Correct 90 ms 15452 KB Output is correct