oj.uz

Submission #1093106

# Submission time Handle Problem Language Result Execution time Memory
1093106 2024-09-26T00:47:33 Z juicy Cities (BOI16_cities) C++17
100 / 100
 1382 ms 41584 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  const long long inf = 1e18;

  int n, k, m; cin >> n >> k >> m;
  vector<int> city(k);
  for (int &u : city) {
    cin >> u; --u;
  }
  vector<vector<array<int, 2>>> g(n);
  while (m--) {
    int u, v, c; cin >> u >> v >> c; --u, --v;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  auto dijkstra = [&](vector<long long> &d) {
    using T = pair<long long, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    for (int i = 0; i < n; ++i) {
      pq.push({d[i], i});
    }
    while (pq.size()) {
      auto [c, u] = pq.top(); pq.pop();
      if (c != d[u]) {
        continue;
      }
      for (auto [v, w] : g[u]) {
        if (d[v] > c + w) {
          pq.push({d[v] = c + w, v});
        }
      }
    }
    return d;
  };
  vector d(1 << k, vector<long long>(n, inf));
  for (int i = 0; i < k; ++i) {
    d[1 << i][city[i]] = 0;
  }
  for (int m = 1; m < 1 << k; ++m) {
    for (int i = 0; i < k; ++i) {
      if (m >> i & 1) {
        for (int j = 0; j < n; ++j) {
          d[m][j] = min(d[m][j], d[m - (1 << i)][j] + d[1 << i][j]);
        }
      }
    }
    dijkstra(d[m]);
  }
  long long res = inf;
  for (int i = 0; i < k; ++i) {
    res = min(res, d.back()[city[i]]);
  }
  cout << res;
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 338 ms 22448 KB Output is correct
2 Correct 321 ms 22168 KB Output is correct
3 Correct 198 ms 15820 KB Output is correct
4 Correct 37 ms 5196 KB Output is correct
5 Correct 169 ms 19968 KB Output is correct
6 Correct 34 ms 5212 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 600 KB Output is correct
2 Correct 4 ms 604 KB Output is correct
3 Correct 3 ms 676 KB Output is correct
4 Correct 2 ms 604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 29036 KB Output is correct
2 Correct 727 ms 28928 KB Output is correct
3 Correct 453 ms 22112 KB Output is correct
4 Correct 413 ms 17316 KB Output is correct
5 Correct 105 ms 8300 KB Output is correct
6 Correct 47 ms 6920 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1382 ms 41180 KB Output is correct
2 Correct 1351 ms 41584 KB Output is correct
3 Correct 1356 ms 41536 KB Output is correct
4 Correct 894 ms 34696 KB Output is correct
5 Correct 765 ms 23524 KB Output is correct
6 Correct 166 ms 9628 KB Output is correct
7 Correct 50 ms 6928 KB Output is correct