Submission #105993

#	Time	Username	Problem	Language	Result	Execution time	Memory
105993		xiaowuc1	Cities (BOI16_cities)	C++14	100 / 100	4468 ms	45096 KiB

cities

#include <algorithm>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
typedef vector<vector<ll>> matrix;

int n, k, m;
int important[5];
vector<pii> edges[100005];
ll dp[100005][32];

void relax(int mask) {
	for(int i = 1; i <= n; i++) {
		int j = mask;
		while(j > 0) {
			dp[i][mask] = min(dp[i][mask], dp[i][j] + dp[i][j^mask]);
			j = (j-1) & mask;
		}
	}
	priority_queue<plli> q;
	for(int i = 1; i <= n; i++) {
		q.push({-dp[i][mask], i});
	}
	while(!q.empty()) {
		plli curr = q.top();
		q.pop();
		if(-curr.first != dp[curr.second][mask]) continue;
		for(pii out: edges[curr.second]) {
			int nextD = out.first;
			ll nextW = -curr.first + out.second;
			if(dp[nextD][mask] > nextW) {
				dp[nextD][mask] = nextW;
				q.push({-dp[nextD][mask], nextD});
			}
		}
	}
}

// init 1-bit
void dijkstra() {
	for(int i = 0; i < k; i++) {
		priority_queue<plli> q;
		q.push({0, important[i]});
		dp[important[i]][1<<i] = 0;
		while(!q.empty()) {
			plli curr = q.top();
			q.pop();
			if(-curr.first != dp[curr.second][1<<i]) continue;
			for(pii out: edges[curr.second]) {
				int nextD = out.first;
				ll nextW = -curr.first + out.second;
				if(dp[nextD][1<<i] > nextW) {
					dp[nextD][1<<i] = nextW;
					q.push({-dp[nextD][1<<i], nextD});
				}
			}
		}
	}
}

void solve() {
	cin >> n >> k >> m;
	for(int i = 1; i <= n; i++) {
		for(int a = 1; a < (1<<k); a++) {
			dp[i][a] = 1e18;
		}
	}
	for(int i = 0; i < k; i++) cin >> important[i];
	while(m--) {
		int a, b, c;
		cin >> a >> b >> c;
		edges[a].push_back({b, c});
		edges[b].push_back({a, c});
	}
	dijkstra();
	for(int mask = 3; mask < (1<<k); mask++) relax(mask);
	ll ret = 1e18;
	for(int i = 1; i <= n; i++) {
		ret = min(ret, dp[i][(1<<k)-1]);
	}
	cout << ret << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
	/*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
	*/
	solve();
}

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