oj.uz

Submission #894263

# Submission time Handle Problem Language Result Execution time Memory
894263 2023-12-28T03:09:20 Z box Cities (BOI16_cities) C++17
100 / 100
 4033 ms 108872 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5, K = 5;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(NULL);
  int n, k, m; cin >> n >> k >> m;
  static int v[K];
  for (int i = 0; i < k; i++) cin >> v[i], v[i]--;
  static vector<pair<int, int>> g[N];
  while (m--) {
    int i, j, w; cin >> i >> j >> w, i--, j--;
    g[i].push_back({j, w}), g[j].push_back({i, w});
  }
  static long long d[K][N];
  for (int s = 0; s < k; s++) {
    long long *t = d[s];
    priority_queue<pair<long long, int>> q;
    memset(t, 0x3f, n * 8);
    q.push({-(t[v[s]] = 0), v[s]});
    while (!q.empty()) {
      auto [x, i] = q.top(); x *= -1, q.pop();
      if (t[i] != x) continue;
      for (auto [j, w] : g[i])
        if (x + w < t[j])
          q.push({-(t[j] = x + w), j});
    }
  }
  static long long f[N][1 << K];
  for (int i = 0; i < n; i++) memset(f[i], 0x3f, (1 << k) * 8);
  priority_queue<tuple<long long, int, int>> q;
  for (int i = 0; i < k; i++) q.push({-(f[v[i]][1 << i] = 0), v[i], 1 << i});
  while (!q.empty()) {
    auto [x, i, b] = q.top(); x *= -1; q.pop();
    if (f[i][b] != x) continue;
    for (auto [j, w] : g[i])
      if (x + w < f[j][b])
        q.push({-(f[j][b] = x + w), j, b});
    for (int s = 0; s < k; s++)
      if ((b >> s & 1) == 0 && x + d[s][i] < f[i][b | (1 << s)])
        q.push({-(f[i][b | 1 << s] = x + d[s][i]), i, b | (1 << s)});
  }
  long long ans = LLONG_MAX;
  for (int i = 0; i < n; i++) ans = min(ans, f[i][(1 << k) - 1]);
  cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4700 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4700 KB Output is correct
4 Correct 3 ms 7004 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 51668 KB Output is correct
2 Correct 770 ms 51784 KB Output is correct
3 Correct 389 ms 42192 KB Output is correct
4 Correct 55 ms 15528 KB Output is correct
5 Correct 433 ms 45348 KB Output is correct
6 Correct 56 ms 15292 KB Output is correct
7 Correct 6 ms 7256 KB Output is correct
8 Correct 4 ms 7260 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9560 KB Output is correct
2 Correct 8 ms 9560 KB Output is correct
3 Correct 6 ms 9564 KB Output is correct
4 Correct 6 ms 7260 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1747 ms 75116 KB Output is correct
2 Correct 1540 ms 74996 KB Output is correct
3 Correct 1119 ms 54520 KB Output is correct
4 Correct 920 ms 49240 KB Output is correct
5 Correct 169 ms 30000 KB Output is correct
6 Correct 70 ms 19364 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3951 ms 108872 KB Output is correct
2 Correct 4033 ms 108116 KB Output is correct
3 Correct 3585 ms 107580 KB Output is correct
4 Correct 2558 ms 102832 KB Output is correct
5 Correct 2047 ms 64500 KB Output is correct
6 Correct 303 ms 29004 KB Output is correct
7 Correct 80 ms 19876 KB Output is correct