oj.uz

Submission #98750

# Submission time Handle Problem Language Result Execution time Memory
98750 2019-02-25T15:05:05 Z youngyojun Cities (BOI16_cities) C++11
100 / 100
 5235 ms 45392 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef priority_queue<pli, vector<pli>, greater<pli>> PQTYPE;

const int MAXN = 100055;
const int MAXM = 200055;

ll D[1<<5][MAXN];

vector<int> G[MAXN];
int A[MAXM], B[MAXM], C[MAXM];
int O[1<<5], T[5];

int N, M, K;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> K >> M;
	for(int i = 1<<K; i--;) fill(D[i], D[i]+N+1, INFLL);
	iota(O, O+(1<<K), 0); sort(O, O+(1<<K), [&](int a, int b) {
		int c = 0;
		for(int i = 0; i < K; i++)
			c += !!(a & (1<<i)) - !!(b & (1<<i));
		return c ? c < 0 : a < b;
	});
	for(int i = 0; i < K; i++) cin >> T[i];
	for(int i = 1, a, b; i <= M; i++) {
		cin >> a >> b >> C[i];
		A[i] = a; B[i] = b;
		G[a].eb(i); G[b].eb(i);
	}
	for(int i = 0, c; i < K; i++) {
		PQTYPE PQ;
		c = T[i];
		D[1<<i][c] = 0;
		PQ.push({0, c});
		for(ll dst; !PQ.empty();) {
			int idx; tie(dst, idx) = PQ.top(); PQ.pop();
			if(D[1<<i][idx] < dst) continue;
			for(int e : G[idx]) {
				ll ndst = dst + C[e];
				int ni = A[e]+B[e]-idx;
				if(D[1<<i][ni] <= ndst) continue;
				D[1<<i][ni] = ndst;
				PQ.push({ndst, ni});
			}
		}
	}
	for(int oi = K+1, i; oi < (1<<K); oi++) {
		i = O[oi];
		for(int j = 1, k; j < i; j++) if((i|j) == i) {
			k = i^j;
			for(int e = 1, a, b; e <= M; e++) {
				a = A[e]; b = B[e];
				ll t = D[j][a] + D[k][b] + C[e];
				if(t < D[i][a]) D[i][a] = t;
				if(t < D[i][b]) D[i][b] = t;
			}
		}
		PQTYPE PQ;
		for(int idx = 1; idx <= N; idx++) PQ.push({D[i][idx], idx});
		for(ll dst; !PQ.empty();) {
			int idx; tie(dst, idx) = PQ.top(); PQ.pop();
			if(D[i][idx] < dst) continue;
			for(int e : G[idx]) {
				ll ndst = dst + C[e];
				int ni = A[e]+B[e]-idx;
				if(D[i][ni] <= ndst) continue;
				D[i][ni] = ndst;
				PQ.push({ndst, ni});
			}
		}
	}
	cout << *min_element(D[(1<<K)-1]+1, D[(1<<K)-1]+N+1) << endl;
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2944 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 6 ms 2816 KB Output is correct
5 Correct 4 ms 2944 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1028 ms 22176 KB Output is correct
2 Correct 1162 ms 22016 KB Output is correct
3 Correct 692 ms 17152 KB Output is correct
4 Correct 136 ms 7644 KB Output is correct
5 Correct 515 ms 16560 KB Output is correct
6 Correct 89 ms 7544 KB Output is correct
7 Correct 8 ms 2944 KB Output is correct
8 Correct 8 ms 3072 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3072 KB Output is correct
2 Correct 10 ms 3072 KB Output is correct
3 Correct 9 ms 3072 KB Output is correct
4 Correct 9 ms 2944 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2318 ms 28488 KB Output is correct
2 Correct 2424 ms 32612 KB Output is correct
3 Correct 1563 ms 25480 KB Output is correct
4 Correct 1317 ms 22636 KB Output is correct
5 Correct 373 ms 13812 KB Output is correct
6 Correct 196 ms 11928 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4867 ms 41140 KB Output is correct
2 Correct 5015 ms 45392 KB Output is correct
3 Correct 5235 ms 45296 KB Output is correct
4 Correct 3330 ms 38184 KB Output is correct
5 Correct 2663 ms 29012 KB Output is correct
6 Correct 789 ms 15252 KB Output is correct
7 Correct 357 ms 12152 KB Output is correct