제출 #826404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826404		serifefedartar	Cities (BOI16_cities)	C++17	100 / 100	1612 ms	48904 KiB

cities

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 20
#define MAXN 100005

vector<vector<pair<int,ll>>> graph;
vector<int> imp;
ll dp[32][MAXN];
int main() {
	fast
	int n, k, m;
	cin >> n >> k >> m;

	graph = vector<vector<pair<int,ll>>>(n, vector<pair<int,ll>>());
	for (int i = 0; i < k; i++) {
		int node; cin >> node;
		node--;
		imp.push_back(node);
	}

	for (int i = 0; i < m; i++) {
		int a, b; 
		ll c;
		cin >> a >> b >> c;
		a--; b--;
		graph[a].push_back({b, c});
		graph[b].push_back({a, c});
	}

	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < MAXN; j++)
			dp[i][j] = 1e15;
	}
	for (int i = 0; i < k; i++) {
		dp[(1<<i)][imp[i]] = 0;
	}

	const int mx_mask = (1<<k) - 1;
	for (int mask = 0; mask <= mx_mask; mask++) {
		for (int comp = 0; comp <= mask; comp++) {
			if ((comp & mask) != comp)
				continue;
			for (int node = 0; node < n; node++)
				dp[mask][node] = min(dp[mask][node], dp[comp][node] + dp[mask ^ comp][node]);
		}

		priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
		for (int node = 0; node < n; node++) {
			if (dp[mask][node] != 1e15)
				pq.push({dp[mask][node], node});
		}

		vector<int> vis(n, false);
		while (!pq.empty()) {
			ll dist = pq.top().f;
			int node = pq.top().s;
			pq.pop();

			if (vis[node])
				continue;
			vis[node] = true;
			for (auto u : graph[node]) {
				ll nDist = u.s;
				int to = u.f;
				if (dist + nDist < dp[mask][to]) {
					dp[mask][to] = dist + nDist;
					pq.push({dp[mask][to], to});
				}
			}
		}
	}

	ll ans = 1e15;
	for (int i = 0; i < n; i++)
		ans = min(ans, dp[mx_mask][i]);
	cout << ans << "\n";
}

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