Submission #253377

#	Time	Username	Problem	Language	Result	Execution time	Memory
253377		Blagojce	Cities (BOI16_cities)	C++11	0 / 100	6062 ms	17364 KiB

cities

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 100005;

int n, k, m;
vector<pii> g[mxn];
vector<int> imp;

ll dist[10][mxn];



vector<int> code;

int deg[10];

ll decode(){
	fr(i, 0, k) deg[i] = 1;
	for(auto u : code){
		++deg[u];
	}
	set<int> leaves;
	fr(i, 0, k){
		if(deg[i] == 1) leaves.insert(i);
	}
	ll sum = 0;
	for(auto u : code){
		int leaf = *leaves.begin();
		leaves.erase(leaves.begin());
		
		sum += dist[leaf][imp[u]];
		--deg[u];
		if(deg[u] == 1) leaves.insert(u);
		
	}
	sum += dist[*leaves.begin()][imp[k-1]];
	return sum;
}
ll best = inf;
void generate_code(int pos){
	if(pos == k-2){
		best = min(best, decode()); 
	}
	else{
		fr(i, 0, k){
			code.pb(i);
			generate_code(pos+1);
			code.pop_back();
		}
	}
}
bool is_imp[mxn];


void solve(){
	cin >> n >> k >> m;
	imp.resize(k);
	fr(i, 0, k) cin >> imp[i];
	fr(i, 0, k) is_imp[--imp[i]] = true;
	
	vector<pair<pii,int> > edges;
	fr(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		edges.pb({{u, v}, w});
		g[u].pb({v, w});
		g[v].pb({u, w});
		
	}
	bool vis[n];
	fr(i, 0, (int)imp.size()){
		memset(vis, false, sizeof(vis));
		fr(j, 0, n) dist[i][j] = inf;
		dist[i][imp[i]] = 0;
		pq<pii> Q;
		Q.push({0, imp[i]});
		while(!Q.empty()){
			int c = Q.top().nd;
			Q.pop();
			if(vis[c]) continue;
			vis[c] = true;
			for(auto e : g[c]){
				if(dist[i][c] + e.nd < dist[i][e.st]){
					dist[i][e.st] = dist[i][c] + e.nd;
					Q.push({-dist[i][e.st], e.st});
				} 
			}
		}
	}
	fr(i, 0, n){
		if(is_imp[i]) continue;
		imp.pb(i);
		fr(j, 0, k){
			dist[k][imp[j]] = dist[j][i];
		}
		++k;
		generate_code(0);
		--k;
		imp.pop_back();
	}
	for(auto u : edges){
		if(is_imp[u.st.st] || is_imp[u.st.nd]) continue;
		imp.pb(u.st.st);
		imp.pb(u.st.nd);
		fr(j, 0, k){
			dist[k][imp[j]] = dist[j][u.st.st];
			dist[k+1][imp[j]] = dist[j][u.st.nd];
		}
		dist[k][u.st.nd] = u.nd;
		dist[k+1][u.st.st] = u.nd; 
		
		k += 2;
		generate_code(0);
		
		imp.pop_back();
		imp.pop_back();
		k -= 2;
	}
	
	
	generate_code(0);	
	cout << best << endl;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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