Submission #745751

#	Time	Username	Problem	Language	Result	Execution time	Memory
745751		vjudge1	Cities (BOI16_cities)	C++17	22 / 100	77 ms	7788 KiB

cities

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 21;

struct DSU {
	vector<int> v;
	DSU(int n) {
		v.resize(n+1);
		for (int i = 1; i <= n; i++) {
			v[i] = i;
		}
	}

	int get(int u) {
		return v[u]==u?u:(v[u] = get(v[u]));
	}

	bool unio(int a, int b) {
		a = get(a); b = get(b);
		if (a == b) return false;
		v[a] = b;
		return true;
	}
};

struct Edge {
	int u, v; ll w;
};

vector<pair<int, ll>> g[MAXN];

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m, k; cin >> n >> k >> m;
	vector<int> imp(k);
	vector<Edge> edges;
	for (int &i : imp) cin >> i;
	for (int i = 0; i < m; i++) {
		Edge e; cin >> e.u >> e.v >> e.w;
		edges.push_back(e);
	}
	sort(edges.begin(), edges.end(), [&](Edge a, Edge b) {
		return a.w < b.w;
	});
	ll ans = 1e16;
	for (int bits = 0; bits < (1 << n); bits++) {
		int b = bits << 1;
		bool g = true;
		for (int i : imp) {
			if (!((b >> i) & 1)) g = false;
		}
		if (!g) continue;
		DSU dsu(n);
		ll res = 0;
		for (Edge e : edges) {
			if (((b>>e.u) & 1) && ((b>>e.v) & 1)) {
				res += dsu.unio(e.u, e.v)*e.w;
			}
		}
		bool bad = false;
		for (int i = 1; i < imp.size(); i++) {
			if (dsu.get(imp[i]) != dsu.get(imp[i-1])) bad = true;
		}
		if (bad) continue;
		ans = min(ans, res);
	}
	cout << ans << "\n";
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int i = 1; i < imp.size(); i++) {
      |                   ~~^~~~~~~~~~~~

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