제출 #484230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484230		Sohsoh84	Cities (BOI16_cities)	C++17	100 / 100	2971 ms	48092 KiB

cities

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e5 + 10;
const ll MAXK = 5;

int n, k, m, ind[MAXN];
ll dp[1 << MAXK][MAXN];
vector<pll> adj[MAXN];
vector<int> vec;

inline void dijkstra(int mask) {
	priority_queue<pll, vector<pll>, greater<pll>> pq;
	for (int i = 1; i <= n; i++) pq.push({dp[mask][i], i});
	
	while (!pq.empty()) {
		int v = pq.top().Y;
		ll d_v = pq.top().X;
		pq.pop();

		if (dp[mask][v] != d_v) continue;

		for (pll e : adj[v]) {
			int u = e.X;
			ll d = e.Y + d_v;

			if (d < dp[mask][u]) {
				dp[mask][u] = d;
				pq.push({d, u});
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> k >> m;
	for (int i = 1; i <= n; i++) ind[i] = k;
	
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		vec.push_back(x);
		ind[x] = i;
	}

	for (int i = 1; i <= m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	for (int i = 0; i < k; i++) {
		memset(dp[1 << i], 63, sizeof dp[1 << i]);
		dp[1 << i][vec[i]] = 0;
		dijkstra(1 << i);
	}

	for (int mask = 0; mask < (1 << k); mask++) {
		if (__builtin_popcount(mask) < 2) continue;
		memset(dp[mask], 63, sizeof dp[mask]);

		for (int v = 1; v <= n; v++) {
			for (pll e : adj[v]) { // wtf
				int w = e.Y, u = e.X;
				for (int submask = mask; submask; submask = (submask - 1) & mask)
					dp[mask][v] = min(dp[mask][v], dp[submask][v] + dp[mask ^ submask][u] + w);
			}
		}

		dijkstra(mask);
	}

	cout << dp[(1 << k) - 1][vec[0]] << endl;	
	return 0;
}

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