oj.uz

Submission #878453

# Submission time Handle Problem Language Result Execution time Memory
878453 2023-11-24T11:35:18 Z nima_aryan Cities (BOI16_cities) C++17
100 / 100
 1650 ms 49252 KB 
/**
 *    author:  NimaAryan
 *    created: 2023-11-24 12:04:17  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr i64 inf = 5E14;

template <typename T = i64>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <typename T = i64>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using Edge = pair<int, i64>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  
  int n, k, m;
  cin >> n >> k >> m;

  vector f(1 << k, vector<i64>(n, inf));

  vector<int> a(k);
  for (int i = 0; i < k; ++i) {
    int x;
    cin >> x;
    --x;
    f[1 << i][x] = 0;
  }

  vector<vector<Edge>> g(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    --a, --b;
    i64 c;
    cin >> c;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }

  for (int S = 1; S < (1 << k); ++S) {
    min_heap<pair<i64, int>> h;
    for (int u = 0; u < n; ++u) {
      for (int T = S; T > 0; T = (T - 1) & S) {
        f[S][u] = min(f[S][u], f[T][u] + f[S ^ T][u]);
      }
      h.emplace(f[S][u], u);
    }
    auto add = [&](int u, i64 c) {
      if (c < f[S][u]) {
        h.emplace(f[S][u] = c, u);
      }
    };
    while (!h.empty()) {
      auto [cd, u] = h.top();
      h.pop();
      if (cd > f[S][u]) {
        continue;
      }
      for (auto [v, w] : g[u]) {
        add(v, f[S][u] + w);
      }
    }
  }

  i64 ans = inf;
  for (int u = 0; u < n; ++u) {
    ans = min(ans, f[(1 << k) - 1][u]);
  }
  cout << ans << "\n";

  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 452 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 30724 KB Output is correct
2 Correct 415 ms 31068 KB Output is correct
3 Correct 217 ms 20024 KB Output is correct
4 Correct 53 ms 13064 KB Output is correct
5 Correct 220 ms 28800 KB Output is correct
6 Correct 50 ms 12944 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 2 ms 588 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 777 ms 38160 KB Output is correct
2 Correct 791 ms 37096 KB Output is correct
3 Correct 499 ms 26428 KB Output is correct
4 Correct 457 ms 26628 KB Output is correct
5 Correct 127 ms 16148 KB Output is correct
6 Correct 53 ms 15548 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1650 ms 49252 KB Output is correct
2 Correct 1623 ms 49128 KB Output is correct
3 Correct 1547 ms 48828 KB Output is correct
4 Correct 1048 ms 39780 KB Output is correct
5 Correct 885 ms 32508 KB Output is correct
6 Correct 188 ms 17432 KB Output is correct
7 Correct 63 ms 15312 KB Output is correct