oj.uz

Submission #952418

# Submission time Handle Problem Language Result Execution time Memory
952418 2024-03-23T20:05:05 Z badont Cities (BOI16_cities) C++17
100 / 100
 1773 ms 50604 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 489 ms 31136 KB Output is correct
2 Correct 420 ms 30512 KB Output is correct
3 Correct 237 ms 20028 KB Output is correct
4 Correct 52 ms 12992 KB Output is correct
5 Correct 214 ms 27200 KB Output is correct
6 Correct 45 ms 12964 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 5 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 604 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 805 ms 37168 KB Output is correct
2 Correct 749 ms 36380 KB Output is correct
3 Correct 536 ms 26384 KB Output is correct
4 Correct 470 ms 26456 KB Output is correct
5 Correct 122 ms 16152 KB Output is correct
6 Correct 65 ms 15376 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1705 ms 50596 KB Output is correct
2 Correct 1773 ms 50604 KB Output is correct
3 Correct 1578 ms 48684 KB Output is correct
4 Correct 1033 ms 39032 KB Output is correct
5 Correct 907 ms 32520 KB Output is correct
6 Correct 194 ms 17660 KB Output is correct
7 Correct 90 ms 15236 KB Output is correct