oj.uz

Submission #89298

# Submission time Handle Problem Language Result Execution time Memory
89298 2018-12-11T15:38:29 Z shoemakerjo Cities (BOI16_cities) C++14
74 / 100
 6000 ms 186548 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 (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 54904 KB Output is correct
2 Correct 42 ms 54904 KB Output is correct
3 Correct 44 ms 55712 KB Output is correct
4 Correct 43 ms 56616 KB Output is correct
5 Correct 45 ms 57504 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 78912 KB Output is correct
2 Correct 1091 ms 82464 KB Output is correct
3 Correct 735 ms 82464 KB Output is correct
4 Correct 140 ms 82464 KB Output is correct
5 Correct 627 ms 92356 KB Output is correct
6 Correct 132 ms 92356 KB Output is correct
7 Correct 47 ms 92356 KB Output is correct
8 Correct 45 ms 92356 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 92356 KB Output is correct
2 Correct 49 ms 92356 KB Output is correct
3 Correct 57 ms 92356 KB Output is correct
4 Correct 48 ms 92356 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 126364 KB Output is correct
2 Correct 2508 ms 129824 KB Output is correct
3 Correct 2304 ms 129824 KB Output is correct
4 Correct 1600 ms 129824 KB Output is correct
5 Correct 408 ms 129824 KB Output is correct
6 Correct 163 ms 129824 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5863 ms 182160 KB Output is correct
2 Execution timed out 6041 ms 186548 KB Time limit exceeded
3 Halted 0 ms 0 KB -