oj.uz

Submission #484230

# Submission time Handle Problem Language Result Execution time Memory
484230 2021-11-02T16:09:12 Z Sohsoh84 Cities (BOI16_cities) C++17
100 / 100
 2971 ms 48092 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e5 + 10;
const ll MAXK = 5;

int n, k, m, ind[MAXN];
ll dp[1 << MAXK][MAXN];
vector<pll> adj[MAXN];
vector<int> vec;

inline void dijkstra(int mask) {
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for (int i = 1; i <= n; i++) pq.push({dp[mask][i], i});
	
	while (!pq.empty()) {
		int v = pq.top().Y;
		ll d_v = pq.top().X;
		pq.pop();

		if (dp[mask][v] != d_v) continue;

		for (pll e : adj[v]) {
			int u = e.X;
			ll d = e.Y + d_v;

			if (d < dp[mask][u]) {
				dp[mask][u] = d;
				pq.push({d, u});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) ind[i] = k;
	
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		vec.push_back(x);
		ind[x] = i;
	}

	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	for (int i = 0; i < k; i++) {
		memset(dp[1 << i], 63, sizeof dp[1 << i]);
		dp[1 << i][vec[i]] = 0;
		dijkstra(1 << i);
	}

	for (int mask = 0; mask < (1 << k); mask++) {
		if (__builtin_popcount(mask) < 2) continue;
		memset(dp[mask], 63, sizeof dp[mask]);

		for (int v = 1; v <= n; v++) {
			for (pll e : adj[v]) { // wtf
				int w = e.Y, u = e.X;
				for (int submask = mask; submask; submask = (submask - 1) & mask)
					dp[mask][v] = min(dp[mask][v], dp[submask][v] + dp[mask ^ submask][u] + w);
			}
		}

		dijkstra(mask);
	}

	cout << dp[(1 << k) - 1][vec[0]] << endl;	
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 2 ms 4940 KB Output is correct
3 Correct 4 ms 8140 KB Output is correct
4 Correct 6 ms 14412 KB Output is correct
5 Correct 10 ms 26828 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 25248 KB Output is correct
2 Correct 551 ms 24692 KB Output is correct
3 Correct 358 ms 17444 KB Output is correct
4 Correct 72 ms 17080 KB Output is correct
5 Correct 289 ms 22140 KB Output is correct
6 Correct 59 ms 13884 KB Output is correct
7 Correct 6 ms 8268 KB Output is correct
8 Correct 3 ms 5196 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 14572 KB Output is correct
2 Correct 11 ms 14540 KB Output is correct
3 Correct 10 ms 14512 KB Output is correct
4 Correct 9 ms 14540 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1303 ms 31404 KB Output is correct
2 Correct 1161 ms 31076 KB Output is correct
3 Correct 741 ms 23560 KB Output is correct
4 Correct 704 ms 28416 KB Output is correct
5 Correct 220 ms 24136 KB Output is correct
6 Correct 116 ms 25620 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2971 ms 44772 KB Output is correct
2 Correct 2971 ms 48092 KB Output is correct
3 Correct 2508 ms 47584 KB Output is correct
4 Correct 1784 ms 38540 KB Output is correct
5 Correct 1538 ms 45188 KB Output is correct
6 Correct 465 ms 40484 KB Output is correct
7 Correct 264 ms 41640 KB Output is correct