Submission #1240165

#TimeUsernameProblemLanguageResultExecution timeMemory
1240165kaiboyCities (BOI16_cities)C++20
100 / 100
823 ms40304 KiB
#pragma GCC optimize("O3") #include <algorithm> #include <iostream> using namespace std; const int N = 100000; const int K = 5; const long long INF = 0x3f3f3f3f3f3f3f3fLL; int hh[N], *ej[N], *ew[N], eo[N]; long long dd[N << K], dd_[N]; int pq[N], iq[N + 1], pq_cnt; void append(int i, int j, int w) { int o = eo[i]++; if (!o) { ej[i] = (int *) malloc(sizeof *ej[i]); ew[i] = (int *) malloc(sizeof *ew[i]); } else { ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]); ew[i] = (int *) realloc(ew[i], (o << 1) * sizeof *ew[i]); } ej[i][o] = j; ew[i][o] = w; } bool lt(int i, int j) { return dd_[i] < dd_[j]; } int p2(int p) { return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p])); } void pq_up(int i) { int j, p, q; for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_dn(int i) { int j, p, q; for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q) iq[pq[j] = p] = j; iq[pq[i] = p] = i; } void pq_add_last(int i) { iq[pq[i] = ++pq_cnt] = i; } int pq_remove_first() { int i = iq[1], j = iq[pq_cnt--]; if (i != j) pq[j] = 1, pq_dn(j); pq[i] = 0; return i; } int main() { ios_base::sync_with_stdio(false), cin.tie(NULL); int n, k, m; cin >> n >> k >> m; for (int i = 0; i < n; i++) hh[i] = -1; for (int h = 0; h < k; h++) { int i; cin >> i, i--; hh[i] = h; } while (m--) { int i, j, w; cin >> i >> j >> w, i--, j--; append(i, j, w), append(j, i, w); } for (int bi = 0; bi < n << k; bi++) dd[bi] = INF; for (int i = 0; i < n; i++) { dd[i] = 0; if (hh[i] != -1) dd[(n << hh[i]) + i] = 0; } for (int b = 0; b < 1 << k; b++) { for (int i = 0; i < n; i++) if ((dd_[i] = dd[b * n + i]) != INF) pq_add_last(i); for (int p = pq_cnt >> 1; p; p--) pq_dn(iq[p]); while (pq_cnt) { int i = pq_remove_first(); for (int o = 0; o < eo[i]; o++) { int j = ej[i][o], w = ew[i][o]; long long d = dd_[i] + w; if (dd_[j] > d) { if (dd_[j] == INF) pq_add_last(j); dd_[j] = d, pq_up(j); } } } for (int c = 0; c < 1 << k; c++) if (!(b & c)) for (int i = 0; i < n; i++) { int bi = (b ^ c) * n + i; dd[bi] = min(dd[bi], dd_[i] + dd[c * n + i]); } } long long ans = INF; for (int i = 0; i < n; i++) ans = min(ans, dd[((1 << k) - 1) * n + i]); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...