oj.uz

Submission #1093101

# Submission time Handle Problem Language Result Execution time Memory
1093101 2024-09-26T00:37:40 Z juicy Cities (BOI16_cities) C++17
100 / 100
 4960 ms 173440 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});
  }
  vector d(n, vector<long long>(1 << k, inf));
  using T = tuple<long long, int, int>;
  priority_queue<T, vector<T>, greater<T>> pq;
  for (int i = 0; i < k; ++i) {
    d[city[i]][1 << i] = 0;
    pq.push({0, city[i], 1 << i});
  }
  while (pq.size()) {
    auto [c, u, m] = pq.top(); pq.pop();
    if (c != d[u][m]) {
      continue;
    }
    for (auto [v, w] : g[u]) {
      if (d[v][m] > c + w) {
        pq.push({d[v][m] = c + w, v, m});
      }
    }
    int mm = (1 << k) - 1 - m;
    for (int sm = mm; sm; sm = (sm - 1) & mm) {
      if (d[u][sm + m] > c + d[u][sm]) {
        pq.push({d[u][sm + m] = c + d[u][sm], u, sm + m});
      }
    }
  }
  long long res = inf;
  for (int i = 0; i < n; ++i) {
    res = min(res, d[i].back());
  }
  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 512 ms 36508 KB Output is correct
2 Correct 402 ms 27540 KB Output is correct
3 Correct 235 ms 21932 KB Output is correct
4 Correct 43 ms 5588 KB Output is correct
5 Correct 192 ms 21360 KB Output is correct
6 Correct 41 ms 5200 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 1 ms 600 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1248 KB Output is correct
2 Correct 5 ms 1116 KB Output is correct
3 Correct 4 ms 860 KB Output is correct
4 Correct 4 ms 1008 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1765 ms 60076 KB Output is correct
2 Correct 1477 ms 63032 KB Output is correct
3 Correct 998 ms 41916 KB Output is correct
4 Correct 705 ms 54284 KB Output is correct
5 Correct 151 ms 19392 KB Output is correct
6 Correct 47 ms 10712 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4784 ms 169344 KB Output is correct
2 Correct 4960 ms 173440 KB Output is correct
3 Correct 4304 ms 173236 KB Output is correct
4 Correct 2757 ms 102992 KB Output is correct
5 Correct 2183 ms 91608 KB Output is correct
6 Correct 288 ms 28784 KB Output is correct
7 Correct 71 ms 12240 KB Output is correct