Submission #878453

#	Time	Username	Problem	Language	Result	Execution time	Memory
878453		nima_aryan	Cities (BOI16_cities)	C++17	100 / 100	1650 ms	49252 KiB

cities

/**
 *    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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26