oj.uz

Submission #98747

# Submission time Handle Problem Language Result Execution time Memory
98747 2019-02-25T15:01:57 Z youngyojun Cities (BOI16_cities) C++11
14 / 100
 1386 ms 40856 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;

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++) {
		priority_queue<pli, vector<pli>, greater<pli>> PQ;
		c = T[i];
		cin >> c;
		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;
			}
		}
	}
	cout << *min_element(D[(1<<K)-1]+1, D[(1<<K)-1]+N+1) << endl;
	return 0;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2944 KB Output is correct
2 Correct 6 ms 2560 KB Output is correct
3 Correct 5 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Incorrect 5 ms 2992 KB Output isn't correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 21700 KB Output is correct
2 Correct 520 ms 22900 KB Output is correct
3 Correct 265 ms 15580 KB Output is correct
4 Correct 135 ms 11228 KB Output is correct
5 Correct 392 ms 18628 KB Output is correct
6 Correct 95 ms 11000 KB Output is correct
7 Correct 7 ms 2916 KB Output is correct
8 Correct 6 ms 2944 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3056 KB Output is correct
2 Incorrect 8 ms 3072 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 797 ms 28112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1386 ms 40856 KB Output isn't correct
2 Halted 0 ms 0 KB -