Submission #522126

#	Time	Username	Problem	Language	Result	Execution time	Memory
522126		sidon	Cities (BOI16_cities)	C++17	100 / 100	1595 ms	40520 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int Z = 1e5, INF = 1e18;
 
int N, K, M, c[5], dp[32][Z];
vector<array<int, 2>> g[Z];
 
int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> N >> K >> M;
 
	for(int i = 0; i < K; ++i)
		cin >> c[i], --c[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});
	}
 
	for(int i = 1; i < (1<<K); ++i)
		fill(dp[i], dp[i] + Z, INF);
 
	for(int i = 0; i < K; ++i)
		dp[1<<i][c[i]] = 0;
 
	for(int i = 1; i < (1<<K); ++i) {
		for(int j = 0; j < K; ++j) if(i & (1<<j)) {
			for(int u = 0; u < N; ++u)
				dp[i][u] = min(dp[i][u], dp[i ^ (1<<j)][u] + dp[1<<j][u]);
		}
 
		int *d = dp[i];
		priority_queue<int> q;
 
		for(int u = 0; u < N; ++u)
			if(d[u] < INF) q.push(-(d[u] * Z + u));
 
		while(!empty(q)) {
			int dist = (-q.top()) / Z, u = (-q.top()) % Z;
			q.pop();
			if(dist != d[u]) continue;
			for(auto &[v, w] : g[u])
				if(d[u] + w < d[v])
					q.push(-((d[v] = d[u] + w) * Z + v));
		}
	}
 
	cout << *min_element(dp[(1<<K)-1], dp[(1<<K)-1] + Z);
}

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