oj.uz

Submission #1048361

# Submission time Handle Problem Language Result Execution time Memory
1048361 2024-08-08T07:04:12 Z TAhmed33 Cities (BOI16_cities) C++
100 / 100
 1332 ms 74792 KB 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,popcnt,lzcnt")
const int MAXN = 2e5 + 25;
typedef long long ll;
const ll inf = 1e16;
vector <pair <int, int>> adj[MAXN];
int n, m, k;
int s[5]; int ind[MAXN];
ll dist[1 << 5][MAXN];
void solve () {
	cin >> n >> k >> m;
	memset(ind, -1, sizeof(ind));
	for (int i = 0; i < k; i++) {
		cin >> s[i]; ind[s[i]] = i;
	}
	for (int i = 1; i <= m; i++) {
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	for (int j = 1; j <= n; j++) {
		for (int i = 0; i < (1 << k); i++) {
			dist[i][j] = inf;
		}
	}
	for (int i = 0; i < k; i++) {
		dist[1 << i][s[i]] = 0;
	}
	for (int i = 1; i <= n; i++) {
		dist[0][i] = 0;
	}
	for (int i = 1; i < (1 << k); i++) {
		for (int z = (i - 1) & i; z > 0; z = (z - 1) & i) {
			for (int j = 1; j <= n; j++) {
				dist[i][j] = min(dist[i][j], dist[z][j] + dist[i ^ z][j]);
			}
		}
		priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater <>> pq;
		for (int j = 1; j <= n; j++) {
			pq.push({dist[i][j], j});
		}
		while (!pq.empty()) {
			auto k = pq.top();
			pq.pop();
			if (k.first > dist[i][k.second]) continue;
			for (auto j : adj[k.second]) {
				if (j.second + k.first < dist[i][j.first]) {
					dist[i][j.first] = j.second + k.first;
					pq.push({dist[i][j.first], j.first});
				}
			}
		}
	}
	ll mn = inf;
	for (int i = 1; i <= n; i++) {
		mn = min(mn, dist[(1 << k) - 1][i]);
	}
	cout << mn << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12764 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 2 ms 18876 KB Output is correct
4 Correct 3 ms 31064 KB Output is correct
5 Correct 5 ms 55780 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 37140 KB Output is correct
2 Correct 311 ms 36108 KB Output is correct
3 Correct 180 ms 27916 KB Output is correct
4 Correct 36 ms 27032 KB Output is correct
5 Correct 171 ms 30304 KB Output is correct
6 Correct 37 ms 20868 KB Output is correct
7 Correct 3 ms 19032 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31272 KB Output is correct
3 Correct 5 ms 31576 KB Output is correct
4 Correct 5 ms 31324 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 49208 KB Output is correct
2 Correct 644 ms 49260 KB Output is correct
3 Correct 389 ms 40440 KB Output is correct
4 Correct 378 ms 44984 KB Output is correct
5 Correct 102 ms 41416 KB Output is correct
6 Correct 43 ms 41084 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1332 ms 74792 KB Output is correct
2 Correct 1125 ms 73688 KB Output is correct
3 Correct 1088 ms 72976 KB Output is correct
4 Correct 708 ms 64900 KB Output is correct
5 Correct 627 ms 69496 KB Output is correct
6 Correct 140 ms 65996 KB Output is correct
7 Correct 45 ms 65676 KB Output is correct