Submission #361262

#	Time	Username	Problem	Language	Result	Execution time	Memory
361262		hoaphat1	Cities (BOI16_cities)	C++17	74 / 100	6070 ms	169980 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);
  vector<int> stt(n + 1, -1);
  for (int i = 0; i < k; i++) {
		cin >> a[i];
		stt[a[i]] = 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);
		for (auto& x : g[v]) {
			int u = x.first;
			for (int to = mask; to < 1 << k; to = (to + 1) | mask) {
				long long val = d[u][to ^ mask] + d[v][mask] + x.second;
				if (d[u][to] > val) {
					d[u][to] = val;
					pq.emplace(-val, u, to);
				}
			}
		}
	}
	long long ans = inf;
	for (int i = 1; i <= n; i++) ans = min(ans, d[i][(1 << k) - 1]);
	cout << ans;
} 

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