oj.uz

Submission #1093100

# Submission time Handle Problem Language Result Execution time Memory
1093100 2024-09-26T00:14:48 Z juicy Cities (BOI16_cities) C++17
14 / 100
 201 ms 18892 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  const long long inf = 1e18;

  int n, k, m; cin >> n >> k >> m;
  vector<int> city(k);
  for (int &u : city) {
    cin >> u; --u;
  }
  vector<vector<array<int, 2>>> g(n);
  while (m--) {
    int u, v, c; cin >> u >> v >> c; --u, --v;
    g[u].push_back({v, c});
    g[v].push_back({u, c});
  }
  auto dijkstra = [&](int s) {
    vector<long long> d(n, inf);
    using T = pair<long long, int>;
    priority_queue<T, vector<T>, greater<T>> pq;
    pq.push({d[s] = 0, s});
    while (pq.size()) {
      auto [c, u] = pq.top(); pq.pop();
      if (c != d[u]) {
        continue;
      }
      for (auto [v, w] : g[u]) {
        if (d[v] > c + w) {
          pq.push({d[v] = c + w, v});
        }
      }
    }
    return d;
  };
  vector<vector<long long>> d(k);
  for (int i = 0; i < k; ++i) {
    d[i] = dijkstra(city[i]);
  }
  vector<long long> dp(1 << k, inf), c(1 << k);
  for (int i = 0; i < k; ++i) {
    dp[1 << i] = 0;
  }
  for (int mask = 1; mask < (1 << k); ++mask) {
    if (__builtin_popcount(mask) > 1) {
      c[mask] = inf;
      for (int i = 0; i < n; ++i) {
        long long w = 0;
        for (int j = 0; j < k; ++j) {
          if (mask >> j & 1) {
            w += d[j][i];
          }
        }
        c[mask] = min(c[mask], w);
      }
    }
  }
  for (int mask = 0; mask < 1 << k; ++mask) {
    for (int smask = mask; smask; smask = (smask - 1) & mask) {
      int x = mask ^ smask;
      long long y = inf;
      for (int i = 0; i < k; ++i) {
        if (x >> i & 1) {
          y = min(y, c[smask + (1 << i)]);
        }
      }
      dp[mask] = min(dp[mask], dp[x] + y);
    }
  }
  cout << dp.back();
  return 0;
}

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 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 17292 KB Output is correct
2 Correct 147 ms 18332 KB Output is correct
3 Correct 48 ms 10320 KB Output is correct
4 Correct 37 ms 8532 KB Output is correct
5 Correct 112 ms 16532 KB Output is correct
6 Correct 37 ms 8532 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

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