oj.uz

Submission #952342

# Submission time Handle Problem Language Result Execution time Memory
952342 2024-03-23T15:01:01 Z badont Cities (BOI16_cities) C++17
0 / 100
 255 ms 27080 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 dist(k, vector<ll>());
  vector par(k, vector<ll>());
  for (int i = 0; i < k; i++) {
    int root = a[i];

    auto &dp = dist[i];
    dp.resize(n, INF);
    auto &parent = par[i];
    parent.resize(n, -1);

    vector<bool> v(n, false);

    priority_queue<pii, vector<pii>, greater<pii>> dij;
    dij.push({0, root});
    dp[root] = 0;

    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 d + w < dp[u]) {
          dp[u] = d + w;
          parent[u] = g;
          dij.push({dp[u], u});
        }
      }
    }
  }

  // debug(dist);

  vector<ll> dp(1 << k, INF);
  vector hit(1 << k, vector<bool>(n, false));
  dp[0] = 0;

  for (int msk = 1; msk < (1 << k); msk++) {
    if (__builtin_popcount(msk) == 1) {
      dp[msk] = 0;
      hit[msk][a[__builtin_ctz(msk)]] = true;
    } else {
      ll best_endp = -1, best_dist = INF, best_startp = -1;
      for (int nn = 0; nn < k; nn++) {
        if (!(msk >> nn & 1))
          continue;

        int pmsk = msk ^ (1 << nn);
        int h = a[nn];
        ll min_dist = INF;
        ll best_transition = -1;
        debug(pmsk, h);
        for (int pi = 0; pi < n; pi++) {
          if (!hit[pmsk][pi])
            continue;
          if (dist[nn][pi] < min_dist) {
            min_dist = dist[nn][pi];
            best_transition = pi;
          }
        }

        if (min_dist + dp[pmsk] < best_dist) {
          best_dist = min_dist + dp[pmsk];
          best_endp = nn;
          best_startp = best_transition;
        }
      }

      assert(best_endp != -1);
      assert(best_startp != -1);
      ll ep = a[best_endp];
      ll c = best_startp;
      hit[msk] = hit[msk ^ (1 << best_endp)];
      while (c != -1) {
        hit[msk][c] = true;
        c = par[best_endp][c];
      }
      dp[msk] = best_dist;
    }
  }

  cout << 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;
}

Compilation message

cities.cpp: In function 'void solve()':
cities.cpp:11:22: warning: statement has no effect [-Wunused-value]
   11 |   #define debug(...) "zzz"
      |                      ^~~~~
cities.cpp:96:9: note: in expansion of macro 'debug'
   96 |         debug(pmsk, h);
      |         ^~~~~
cities.cpp:93:13: warning: unused variable 'h' [-Wunused-variable]
   93 |         int h = a[nn];
      |             ^
cities.cpp:115:10: warning: unused variable 'ep' [-Wunused-variable]
  115 |       ll ep = a[best_endp];
      |          ^~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 180 ms 23884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 25440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 255 ms 27080 KB Output isn't correct
2 Halted 0 ms 0 KB -