Submission #1048361

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048361		TAhmed33	Cities (BOI16_cities)	C++98	100 / 100	1332 ms	74792 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26