Submission #89299

#	Time	Username	Problem	Language	Result	Execution time	Memory
89299		shoemakerjo	Cities (BOI16_cities)	C++14	100 / 100	5859 ms	137008 KiB

cities

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pp pair<ll, pair<int, int>>

#define mp make_pair
#define maxn 100010
#define maxm 200010

int n, k, m;

const ll inf = 1e16;

ll val[(1 << 6)][maxn]; //start all at infinity
ll dist[6][maxn]; //distance from all terminals
vector<pil> adj[maxn];

int terminal[maxn];
int indo[maxn];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k >> m;

	//modified dijkstra (spiderman algorithm)
	for (int i = 0; i < k; i++) {
		cin >> terminal[i];
		indo[terminal[i]] = i;
	}

	for (int j = 0; j < (1 << 6);  ++j) {
		fill(val[j], val[j] + maxn, inf);
	}
	fill(indo, indo+maxn, -1);

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

	int cmask;
	int spot;
	ll di;
	//must do my dijkstra for all terminals
	for (int i = 0; i < k; i++) {
		priority_queue<pli, vector<pli>, greater<pli>> q;
		fill(dist[i], dist[i]+maxn, inf);
		q.push(mp(0LL, terminal[i]));
		dist[i][terminal[i]] = 0LL;

		while (q.size()) {
			pli tmp = q.top(); q.pop();
			di = tmp.first;
			spot = tmp.second;
			if (di > dist[i][spot]) continue;
			for (pli vp : adj[spot]) {
				ll nx = di + vp.second;
				if (nx < dist[i][vp.first]) {
					dist[i][vp.first] = nx;
					q.push(mp(nx, vp.first));
				}
			}
		}

		// for (int j = 1; j <= n; j++) {
		// 	cout << "dist from " << terminal[i] << " to " << 
		// 		j << " is " << dist[i][j] << endl;
		// }
	}

	priority_queue<pp, vector<pp>, greater<pp>> pq;
	for (int j = 1; j <= n; j++) {
		pq.push(mp(0LL, mp(0, j)));
	}

	// cout << "here here here " << endl;
	
	while (pq.size()) {
		pp cur = pq.top(); pq.pop();
		cmask = cur.second.first;

		spot = cur.second.second;
		di = cur.first;

		if (cmask == (1 << k) - 1) {
			cout << di << endl;
			return 0;
		}

		if (val[cmask][spot] < di) continue;

		for (int j = 0; j < k; j++) {
			if (cmask & (1 << j)) continue;
			int nmask = cmask + (1 << j);
			ll nx = di + dist[j][spot];
			if (nx < val[nmask][spot]) {
				val[nmask][spot] = nx;
				pq.push(mp(nx, mp(nmask, spot)));
			}
		}

		for (pil vp : adj[spot]) {
			ll nx = di + vp.second;
			if (nx < val[cmask][vp.first]) {
				val[cmask][vp.first] = nx;
				pq.push(mp(nx, mp(cmask, vp.first)));
			}
			
		}
	}

	ll ans = inf;
	for (int j = 1; j <= n; j++) {
		ans = min(ans, val[(1 << k)-1][j]);
	}
	cout << ans << endl;
}

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