oj.uz

Submission #484228

# Submission time Handle Problem Language Result Execution time Memory
484228 2021-11-02T15:59:59 Z Sohsoh84 Cities (BOI16_cities) C++17
52 / 100
 2402 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 = 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 47272 KB Output is correct
2 Correct 19 ms 47312 KB Output is correct
3 Correct 31 ms 78500 KB Output is correct
4 Correct 54 ms 141224 KB Output is correct
5 Runtime error 102 ms 262148 KB Execution killed with signal 9

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 562 ms 96256 KB Output is correct
2 Correct 550 ms 99444 KB Output is correct
3 Correct 344 ms 89920 KB Output is correct
4 Correct 108 ms 91020 KB Output is correct
5 Correct 286 ms 68484 KB Output is correct
6 Correct 73 ms 59664 KB Output is correct
7 Correct 35 ms 78788 KB Output is correct
8 Correct 21 ms 47436 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 141388 KB Output is correct
2 Correct 60 ms 141432 KB Output is correct
3 Correct 58 ms 141324 KB Output is correct
4 Correct 58 ms 141408 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1250 ms 158796 KB Output is correct
2 Correct 1197 ms 162156 KB Output is correct
3 Correct 768 ms 152496 KB Output is correct
4 Correct 737 ms 159524 KB Output is correct
5 Correct 264 ms 154864 KB Output is correct
6 Correct 181 ms 155864 KB Output is correct

Subtask #5
0 / 26.0

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