Submission #1075354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075354		vjudge1	Cities (BOI16_cities)	C++17	100 / 100	1266 ms	46276 KiB

cities

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair

const int NM = 1e5, KM = 5, inf = 1e18;

int n, k, m, f[KM+5];
vector <pii> adj[NM+5];
int d[(1<<KM)+5][NM+5];
priority_queue <pii, vector <pii>, greater <pii> > pq;
int ans = +inf;

void solve(){
	for (int msk = 1; msk < (1<<k); msk++){
		for (int i = 1; i <= n; i++) d[msk][i] = +inf;
		if (__builtin_popcount(msk) == 1) d[msk][f[__lg(msk)]] = 0;
		while (!pq.empty()) pq.pop();
		for (int i = 1; i <= n; i++){
			for (int j = (msk-1)&msk; j > 0; j = (j-1)&msk){
				d[msk][i] = min(d[msk][i], d[j][i]+d[msk-j][i]);
			}
			pq.push(mp(d[msk][i], i));
		}
		while (!pq.empty()){
			if (d[msk][pq.top().se] != pq.top().fi){
				pq.pop();
				continue;
			}
			int u = pq.top().se; pq.pop();
			for (pii _ : adj[u]){
				int v = _.fi, c = _.se;
				if (d[msk][u]+c < d[msk][v]){
					d[msk][v] = d[msk][u]+c;
					pq.push(mp(d[msk][v], v));
				}
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> k >> m;
	for (int i = 0; i < k; i++)
		cin >> f[i];
	while (m--){
		int u, v, c;
		cin >> u >> v >> c;
		adj[u].push_back(mp(v, c));
		adj[v].push_back(mp(u, c));
	}
	solve();
	for (int i = 1; i <= n; i++)
		ans = min(ans, d[(1<<k)-1][i]);
	cout << ans;
	return 0;
}

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