oj.uz

Submission #89299

# Submission time Handle Problem Language Result Execution time Memory
89299 2018-12-11T15:40:01 Z shoemakerjo Cities (BOI16_cities) C++14
100 / 100
 5859 ms 137008 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 54776 KB Output is correct
2 Correct 42 ms 54840 KB Output is correct
3 Correct 47 ms 55660 KB Output is correct
4 Correct 45 ms 56560 KB Output is correct
5 Correct 46 ms 57408 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 74480 KB Output is correct
2 Correct 1121 ms 74480 KB Output is correct
3 Correct 407 ms 74480 KB Output is correct
4 Correct 133 ms 74480 KB Output is correct
5 Correct 526 ms 74480 KB Output is correct
6 Correct 130 ms 74480 KB Output is correct
7 Correct 46 ms 74480 KB Output is correct
8 Correct 44 ms 74480 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 74480 KB Output is correct
2 Correct 51 ms 74480 KB Output is correct
3 Correct 48 ms 74480 KB Output is correct
4 Correct 47 ms 74480 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2389 ms 99904 KB Output is correct
2 Correct 1898 ms 99904 KB Output is correct
3 Correct 1413 ms 99904 KB Output is correct
4 Correct 1270 ms 99904 KB Output is correct
5 Correct 316 ms 99904 KB Output is correct
6 Correct 157 ms 99904 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5859 ms 133552 KB Output is correct
2 Correct 5058 ms 133620 KB Output is correct
3 Correct 4509 ms 137008 KB Output is correct
4 Correct 2997 ms 137008 KB Output is correct
5 Correct 2597 ms 137008 KB Output is correct
6 Correct 522 ms 137008 KB Output is correct
7 Correct 167 ms 137008 KB Output is correct