Submission #361264

#	Time	Username	Problem	Language	Result	Execution time	Memory
361264		hoaphat1	Cities (BOI16_cities)	C++17	100 / 100	5861 ms	108348 KiB

cities

#include<bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,k,m;
  cin >> n >> k >> m;
  vector<int> a(k);
  for (int i = 0; i < k; i++) {
		cin >> a[i];
	}
	vector<vector<pair<int,int>>> g(n + 1);
	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v, w);
		g[v].emplace_back(u, w);
	}
	const long long inf = 1e18;
  vector<vector<long long>> d(n + 1, vector<long long> (1 << k, inf));
  priority_queue<tuple<long long, int, int>> pq;
  for (int i = 0; i < k; i++) {
  	d[a[i]][1 << i] = 0;
  	pq.emplace(0, a[i], 1 << i);
	}
	for (int i = 1; i <= n; i++) {
		d[i][0] = 0;
		pq.emplace(0, i, 0);
	}
	while (!pq.empty()) {
		auto x = pq.top();pq.pop();
		if (-get<0>(x) != d[get<1>(x)][get<2>(x)]) continue;
		int v = get<1>(x);
		int mask = get<2>(x);
		if (mask == (1 << k) - 1) return cout << -get<0>(x), 0;
		for (int i = 0; i < k; i++) {
			if (mask >> i & 1) continue;
			if (d[v][mask] + d[v][1 << i] < d[v][mask | (1 << i)]) {
				d[v][mask | (1 << i)] = d[v][mask] + d[v][1 << i];
				pq.emplace(-d[v][mask | (1 << i)], v, mask | (1 << i));
			}
		}
		for (auto& x : g[v]) {
			int u = x.first;
			if (d[u][mask] > d[v][mask] + x.second) {
				d[u][mask] = d[v][mask] + x.second;
				pq.emplace(-d[u][mask], u, mask);
			}
		}
	}
	assert(false);
} 

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26