제출 #952418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952418		badont	Cities (BOI16_cities)	C++17	100 / 100	1773 ms	50604 KiB

cities

#include <bits/stdc++.h>
using namespace std;

// clang-format off
template <typename T, typename = void> struct is_iterable : false_type {};template <typename T>struct is_iterable<    T, void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>>    : true_type {};template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value,ostream &>::type operator<<(ostream &cout, T const &v);template <typename A, typename B>ostream &operator<<(ostream &cout, pair<A, B> const &p) {  return cout << "(" << p.first << ", " << p.second << ")";}template <typename T>typename enable_if<is_iterable<T>::value && !is_same<T, string>::value, ostream &>::type operator<<(ostream &cout, T const &v) {  cout << "[";  for (auto it = v.begin(); it != v.end();) {cout << *it; if (++it != v.end()) cout << ", ";  } return cout << "]";}

#ifdef LOCAL
  void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
  #define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
  #define debug(...) "zzz"
#endif
// clang-format on

using ll = long long;
using ld = long double;
using pii = pair<ll, ll>;

#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

void solve() {
  // open
  ll n, m, k;
  cin >> n >> k >> m;

  vector<ll> a(k);
  for (auto &u : a)
    cin >> u, u--;

  vector e(n, vector<pii>());
  for (int i = 0; i < m; i++) {
    ll x, y, d;
    cin >> x >> y >> d;
    x--, y--;
    e[x].pb({y, d});
    e[y].pb({x, d});
  }

  constexpr ll INF = 1e18;
  vector dp(1 << k, vector<ll>(n, INF));

  for (int i = 0; i < k; i++) {
    dp[1 << i][a[i]] = 0;
  }

  // debug(dp);

  for (int msk = 1; msk < (1 << k); msk++) {
    // two edges
    for (int pmsk = msk; pmsk > 0; pmsk = (pmsk - 1) & msk) {
      if (pmsk == msk)
        continue;

      int omsk = msk ^ pmsk;
      for (int i = 0; i < n; i++) {
        // combine two rooted trees
        // minimizer of trees that connect 5 nodes can be built this way too
        dp[msk][i] = min(dp[msk][i], dp[pmsk][i] + dp[omsk][i]);
      }
    }

    // debug(dp[msk]);

    // one edge
    auto &dist = dp[msk];
    vector<bool> v(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> dij;
    for (int i = 0; i < n; i++) {
      dij.push({dist[i], i});
    }

    while (!dij.empty()) {
      auto [d, g] = dij.top();
      dij.pop();
      if (v[g])
        continue;

      v[g] = true;
      for (auto [u, w] : e[g]) {
        if (!v[u] and dist[u] > dist[g] + w) {
          dist[u] = dist[g] + w;
          dij.push({dist[u], u});
        }
      }
    }
  }

  cout << *min_element(all(dp[(1 << k) - 1])) << '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(false);

  ll T = 1;
  // cin >> T;
  for (int t = 0; t < T; t++)
    solve();

  cout.flush();
  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26