Submission #98750

#	Time	Username	Problem	Language	Result	Execution time	Memory
98750		youngyojun	Cities (BOI16_cities)	C++11	100 / 100	5235 ms	45392 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26