제출 #253871

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253871		super_j6	Cities (BOI16_cities)	C++14	0 / 100	6079 ms	17912 KiB

cities

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, ll>
#define vi vector<int>
#define pv pair<ll, vi>
#define f first
#define s second
 
ll inf = 0x3f3f3f3f3f3f3f3f;
const int mxn = 100000;
int n, m, k;
vi a;
ll d[mxn], p[mxn], vis[mxn];
vector<pi> g[mxn];
set<pi> pq;

pv sol(vi v){
	int f = v.size();
	if(!~-f) return {0, v};
	pv ret = {inf, vi()};
	for(int b = (1 << (f - 1)); b < (1 << f) - 1; b++){
		pv cur = {0, vi()};
		vi s[2];
		for(int i = 0; i < f; i++) s[(b >> i) & 1].push_back(v[i]);
		for(int i = 0; i < 2; i++){
			pv x = sol(s[i]);
			cur.f += x.f, cur.s.insert(cur.s.end(), s[i].begin(), s[i].end()), s[i] = x.s;
		}
		sort(cur.s.begin(), cur.s.end());
		cur.s.erase(unique(cur.s.begin(), cur.s.end()), cur.s.end());
		memset(d, inf, sizeof(d));
		memset(vis, 0, sizeof(vis));
		for(int i : s[0]){
			d[i] = 0, p[i] = -1;
			pq.insert({0, i});
		}
		for(int i : s[1]) vis[i] = 1;
		while(!pq.empty()){
			int c = pq.begin()->s;
			pq.erase(pq.begin());
			if(vis[c]){
				while(!pq.empty()) pq.erase(pq.begin());
				cur.f += d[c];
				for(int i = c; ~i; i = p[i]) cur.s.push_back(i);
				break;
			}
			for(pi i : g[c]){
				if(d[c] + i.s < d[i.f]){
					pq.erase({d[i.f], i.f});
					pq.insert({d[i.f] = d[p[i.f] = c] + i.s, i.f});
				}
			}
		}
		ret = min(ret, cur);
	}
	return ret;
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n >> k >> m;
 
	a.resize(k);
	for(int i = 0; i < k; i++){
		cin >> a[i];
		a[i]--;
	}
 
	for(int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
 
	cout << sol(a).f << endl;
 
	return 0;
}

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