Submission #391067

#	Time	Username	Problem	Language	Result	Execution time	Memory
391067		nikatamliani	Cities (BOI16_cities)	C++14	0 / 100	5388 ms	20224 KiB

cities

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+10;
const ll oo = 1e18;
ll n, k, m, important[10];
vector<pair<ll, ll>> edges[N];
int dijkstra(vector<bool> &visited, int x) {
	priority_queue<pair<ll, ll>> q;
	q.push({0, x});
	vector<ll> dist((int)visited.size(), oo);
	vector<ll> parent((int)visited.size());
	ll last = -1; 
	dist[x] = 0; 
	while(!q.empty()) {
		pair<ll, ll> p = q.top(); q.pop();
		if(dist[p.second] != -p.first) continue;
		if(visited[p.second]) {
			last = p.second;
			break;
		}
		for(pair<ll, ll> to : edges[p.second]) {
			ll dst = -p.first + to.second;
			if(dist[to.first] > dst) {
				dist[to.first] = dst;
				parent[to.first] = p.second; 
				q.push({-dst, to.first});
			}
		}
	}
	assert(last != -1);
	ll cost = 0; 
	cost += dist[last];
	while(last != x) {
		visited[last] = 1; 
		last = parent[last];
	}
	visited[last] = 1;
	return cost;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> m;
	for(int i = 0; i < k; ++i) {
		cin >> important[i];
		--important[i];
	}
	for(int i = 0; i < m; ++i) {
		ll u, v, c;
		cin >> u >> v >> c;
		--u, --v; 
		edges[u].push_back({v, c}); 
		edges[v].push_back({u, c});
	}
	vector<int> perm(k);
	iota(perm.begin(), perm.end(), 0);  
	ll ans = oo;
	do {
		vector<bool> visited(n);
		visited[important[perm[0]]] = 1;
		ll cost = 0;
		for(int i = 1; i < (int)perm.size(); ++i) {
			cost += dijkstra(visited, important[perm[i]]);
		}
		ans = min(ans, cost);
	} while(next_permutation(perm.begin(), perm.end()));
	cout << ans << endl;
}

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