# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
161954 | 2019-11-05T11:55:46 Z | SamAnd | Cities (BOI16_cities) | C++17 | 3684 ms | 49880 KB |
#include <bits/stdc++.h> using namespace std; const int N = 100005, K = 5; const long long INF = 1000000009000000009; struct ban { int x; long long d; ban(){} ban(int x, long long d) { this->x = x; this->d = d; } }; bool operator<(const ban& a, const ban& b) { return a.d > b.d; } int n, k, m; int u[K]; vector<ban> a[N]; long long dp[N][1 << K]; bool c[N]; void djk(int x) { memset(c, false, sizeof c); priority_queue<ban> q; for (int i = 1; i <= n; ++i) q.push(ban(i, dp[i][x])); while (1) { ban t; do { if (q.empty()) { return; } t = q.top(); q.pop(); } while (c[t.x]); c[t.x] = true; dp[t.x][x] = t.d; for (int i = 0; i < a[t.x].size(); ++i) { ban h = a[t.x][i]; h.d += t.d; if (!c[h.x]) q.push(h); } } } int main() { scanf("%d%d%d", &n, &k, &m); for (int i = 0; i < k; ++i) scanf("%d", &u[i]); for (int i = 0; i < m; ++i) { int x, y, z; scanf("%d%d%d", &x, &y, &z); a[x].push_back(ban(y, z)); a[y].push_back(ban(x, z)); } for (int x = 0; x < (1 << k); ++x) { for (int i = 1; i <= n; ++i) dp[i][x] = INF; } for (int x = 1; x < (1 << k); ++x) { int qq = 0, ii; for (int i = 0; i < k; ++i) { if ((x & (1 << i))) { ++qq; ii = i; } } if (qq == 1) { dp[u[ii]][x] = 0; } for (int i = 1; i <= n; ++i) { for (int y = 0; y < k; ++y) { if (!(x & (1 << y))) continue; int z = (x ^ (1 << y)); dp[i][x] = min(dp[i][x], dp[i][z] + dp[i][(1 << y)]); } } djk(x); } long long ans = INF; for (int i = 1; i <= n; ++i) ans = min(ans, dp[i][(1 << k) - 1]); printf("%lld\n", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2936 KB | Output is correct |
2 | Correct | 4 ms | 2808 KB | Output is correct |
3 | Correct | 5 ms | 2808 KB | Output is correct |
4 | Correct | 5 ms | 2808 KB | Output is correct |
5 | Correct | 5 ms | 2808 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 955 ms | 49572 KB | Output is correct |
2 | Correct | 888 ms | 49164 KB | Output is correct |
3 | Correct | 494 ms | 39008 KB | Output is correct |
4 | Correct | 421 ms | 22592 KB | Output is correct |
5 | Correct | 488 ms | 49564 KB | Output is correct |
6 | Correct | 244 ms | 22376 KB | Output is correct |
7 | Correct | 8 ms | 3192 KB | Output is correct |
8 | Correct | 7 ms | 3320 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 3192 KB | Output is correct |
2 | Correct | 11 ms | 3320 KB | Output is correct |
3 | Correct | 9 ms | 3192 KB | Output is correct |
4 | Correct | 11 ms | 3064 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1683 ms | 49596 KB | Output is correct |
2 | Correct | 1623 ms | 49180 KB | Output is correct |
3 | Correct | 1076 ms | 39116 KB | Output is correct |
4 | Correct | 1312 ms | 36996 KB | Output is correct |
5 | Correct | 882 ms | 25416 KB | Output is correct |
6 | Correct | 796 ms | 24756 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 3420 ms | 49880 KB | Output is correct |
2 | Correct | 3572 ms | 49836 KB | Output is correct |
3 | Correct | 3684 ms | 49260 KB | Output is correct |
4 | Correct | 2024 ms | 39080 KB | Output is correct |
5 | Correct | 2354 ms | 37268 KB | Output is correct |
6 | Correct | 1631 ms | 25344 KB | Output is correct |
7 | Correct | 1542 ms | 24900 KB | Output is correct |