# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
310326 | 2020-10-06T16:31:32 Z | BeanZ | Cities (BOI16_cities) | C++14 | 2606 ms | 44992 KB |
// I_Love_LPL #include <bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' const int N = 1e5 + 5; const int mod = 1e9 + 7; ll dp[(1 << 5) + 1][N], p[N]; vector<pair<ll, ll>> node[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("A.inp", "r")){ freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout); } ll n, k, m; cin >> n >> k >> m; for (int i = 0; i < (1 << k); i++){ for (int j = 1; j <= n; j++){ dp[i][j] = 1e18; } } for (int i = 0; i < k; i++) cin >> p[i], dp[(1 << i)][p[i]] = 0; for (int i = 1; i <= m; i++){ ll u, v, c; cin >> u >> v >> c; node[u].push_back({v, c}); node[v].push_back({u, c}); } for (int i = 1; i < (1 << k); i++){ for (int j = 0; j < k; j++){ if (!(i & (1 << j))) continue; ll mask = i ^ (1 << j); for (int u = 1; u <= n; u++){ dp[i][u] = min(dp[i][u], dp[mask][u] + dp[(1 << j)][u]); } } priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq; for (int j = 1; j <= n; j++){ //cout << dp[i][j] << i << " " << j << endl; pq.push({dp[i][j], j}); } while (pq.size()){ pair<ll, ll> x = pq.top(); pq.pop(); if (x.first != dp[i][x.second]) continue; for (auto j : node[x.second]){ if ((x.first + j.second) < dp[i][j.first]){ dp[i][j.first] = x.first + j.second; pq.push({dp[i][j.first], j.first}); } } } } ll ans = 1e18; for (int i = 1; i <= n; i++){ ans = min(ans, dp[(1 << k) - 1][i]); } cout << ans; } /* */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2688 KB | Output is correct |
2 | Correct | 2 ms | 2688 KB | Output is correct |
3 | Correct | 2 ms | 2688 KB | Output is correct |
4 | Correct | 3 ms | 2816 KB | Output is correct |
5 | Correct | 2 ms | 2816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 730 ms | 25948 KB | Output is correct |
2 | Correct | 678 ms | 25464 KB | Output is correct |
3 | Correct | 475 ms | 17888 KB | Output is correct |
4 | Correct | 79 ms | 11768 KB | Output is correct |
5 | Correct | 389 ms | 22740 KB | Output is correct |
6 | Correct | 72 ms | 11688 KB | Output is correct |
7 | Correct | 5 ms | 2944 KB | Output is correct |
8 | Correct | 4 ms | 2944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 3072 KB | Output is correct |
2 | Correct | 7 ms | 3072 KB | Output is correct |
3 | Correct | 7 ms | 2944 KB | Output is correct |
4 | Correct | 6 ms | 2944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1366 ms | 32220 KB | Output is correct |
2 | Correct | 1340 ms | 31808 KB | Output is correct |
3 | Correct | 885 ms | 24152 KB | Output is correct |
4 | Correct | 716 ms | 23052 KB | Output is correct |
5 | Correct | 192 ms | 14668 KB | Output is correct |
6 | Correct | 92 ms | 14288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2606 ms | 44992 KB | Output is correct |
2 | Correct | 2553 ms | 44636 KB | Output is correct |
3 | Correct | 2512 ms | 44312 KB | Output is correct |
4 | Correct | 1703 ms | 37000 KB | Output is correct |
5 | Correct | 1315 ms | 29584 KB | Output is correct |
6 | Correct | 289 ms | 16020 KB | Output is correct |
7 | Correct | 98 ms | 14144 KB | Output is correct |