Submission #745757

#	Time	Username	Problem	Language	Result	Execution time	Memory
745757		vjudge1	Cities (BOI16_cities)	C++17	22 / 100	233 ms	7012 KiB

cities

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

struct edge {
	int a, b;
	ll w;
};

const int maxn = 21;
int p[maxn], s[maxn];
int hol(int x) {
	return p[x]==x?x:p[x]=hol(p[x]);
}
bool unio(int u, int v) {
	u = hol(u), v = hol(v);
	if (u == v)return false;
	if (s[u] < s[v])swap(u, v);	
	p[v] = u;
	s[u] += s[v];
	return true;
}

vector<edge> edges;
vector<int> imp;
ll check(int mask) {
	for (int i = 0; i < 21; i++)p[i] = i;
	ll ans = 0;
	for (auto i : edges) {
		if (((1<<i.a)&mask) != 0 && ((1<<i.b)&mask) != 0 && unio(i.a, i.b))ans += i.w;
	}
	for (int i = 0; i < imp.size() - 1; i++) {
		if (hol(imp[i]) != hol(imp[i + 1]))return -1;
	}
	return ans;
}

int main()
{
	int n, k, m;
	cin >> n >> k >> m;
	imp.resize(k);
	for (int i = 0; i < k; i++) {
		cin >> imp[i];
		imp[i]--;
	}
	for (int i = 0; i < m; i++) {
		int a, b;
		ll w;
		cin >> a >> b >> w;
		edges.push_back({ a-1, b-1, w });
	}
	sort(edges.begin(), edges.end(), [](edge& a, edge&b) {return a.w < b.w; });
	ll ans = INT64_MAX;
	for (int i = 0; i < (1 << n); i++) {
		ll x = check(i);
		if (x >= 0)ans = min(ans, x);
	}
	cout << ans << endl;
}

Compilation message (stderr)

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

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