oj.uz

Submission #484229

# Submission time Handle Problem Language Result Execution time Memory
484229 2021-11-02T16:06:51 Z Sohsoh84 Cities (BOI16_cities) C++17
52 / 100
 2363 ms 262148 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 = 1e6 + 10;
const ll MAXK = 6;

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

# Verdict Execution time Memory Grader output
1 Correct 20 ms 47180 KB Output is correct
2 Correct 19 ms 47180 KB Output is correct
3 Correct 30 ms 78528 KB Output is correct
4 Correct 54 ms 141116 KB Output is correct
5 Runtime error 113 ms 262148 KB Execution killed with signal 9

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 95572 KB Output is correct
2 Correct 522 ms 95476 KB Output is correct
3 Correct 361 ms 88004 KB Output is correct
4 Correct 96 ms 87608 KB Output is correct
5 Correct 304 ms 64408 KB Output is correct
6 Correct 78 ms 56260 KB Output is correct
7 Correct 32 ms 78788 KB Output is correct
8 Correct 20 ms 47504 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 141272 KB Output is correct
2 Correct 59 ms 141380 KB Output is correct
3 Correct 58 ms 141328 KB Output is correct
4 Correct 66 ms 141508 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 158304 KB Output is correct
2 Correct 1136 ms 158036 KB Output is correct
3 Correct 761 ms 150600 KB Output is correct
4 Correct 703 ms 155372 KB Output is correct
5 Correct 252 ms 150968 KB Output is correct
6 Correct 166 ms 152624 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 2363 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -