oj.uz

Submission #679665

# Submission time Handle Problem Language Result Execution time Memory
679665 2023-01-08T20:32:33 Z peijar Cities (BOI16_cities) C++17
100 / 100
 5494 ms 237556 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
  out << "[";
  for (int i = 0; i < (int)vec.size(); ++i) {
    out << vec[i];
    if (i + 1 < (int)vec.size())
      out << ", ";
  }
  return out << "]";
}
} // namespace std

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << H;
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

const int MAXK = 5;
const int MAXN = 1e5;
const int INF = 1e18;
int dp[MAXN][1 << MAXK];
vector<pair<int, int>> adj[MAXN];

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommet, nbImportants, nbAretes;
  cin >> nbSommet >> nbImportants >> nbAretes;
  vector<int> importants(nbImportants);
  for (int &x : importants) {
    cin >> x;
    --x;
  }
  for (int i = 0; i < nbAretes; ++i) {
    int u, v, c;
    cin >> u >> v >> c;
    --u, --v;
    adj[u].emplace_back(v, c);
    adj[v].emplace_back(u, c);
  }

  auto compare = [&](tuple<int, int, int> l, tuple<int, int, int> r) {
    return get<2>(l) > get<2>(r);
  };

  priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>,
                 decltype(compare)>
      pq(compare);
  for (int i = 0; i < nbSommet; ++i)
    for (int msk = 0; msk < (1 << nbImportants); ++msk)
      dp[i][msk] = INF;

  for (int i = 0; i < nbImportants; ++i) {
    dp[importants[i]][1 << i] = 0;
    pq.emplace(importants[i], 1 << i, 0);
  }
  vector<vector<int>> seen(nbSommet);

  while (!pq.empty()) {
    auto [u, msk, cost] = pq.top();
    pq.pop();
    if (dp[u][msk] < cost)
      continue;
    if (msk == ((1 << nbImportants) - 1)) {
      cout << cost << endl;
      return 0;
    }
    for (int msk2 = (1 << nbImportants) - 1 - msk; msk2;
         msk2 = (msk2 - 1) & ((1 << nbImportants) - 1 - msk))
      if (dp[u][msk | msk2] > dp[u][msk] + dp[u][msk2]) {
        dp[u][msk | msk2] = dp[u][msk] + dp[u][msk2];
        pq.emplace(u, msk | msk2, dp[u][msk | msk2]);
      }
    for (auto [v, w] : adj[u])
      if (dp[v][msk] > dp[u][msk] + w) {
        dp[v][msk] = dp[u][msk] + w;
        pq.emplace(v, msk, dp[u][msk]);
      }
  }
  int sol = INF;
  for (int u = 0; u < nbSommet; ++u)
    sol = min(sol, dp[u][(1 << nbImportants) - 1]);
  cout << sol << endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 65136 KB Output is correct
2 Correct 571 ms 52284 KB Output is correct
3 Correct 103 ms 36984 KB Output is correct
4 Correct 69 ms 13388 KB Output is correct
5 Correct 288 ms 46904 KB Output is correct
6 Correct 53 ms 12636 KB Output is correct
7 Correct 4 ms 3284 KB Output is correct
8 Correct 3 ms 3028 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3920 KB Output is correct
2 Correct 7 ms 3920 KB Output is correct
3 Correct 4 ms 3276 KB Output is correct
4 Correct 5 ms 3348 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2146 ms 138928 KB Output is correct
2 Correct 1795 ms 138380 KB Output is correct
3 Correct 848 ms 60104 KB Output is correct
4 Correct 1258 ms 76272 KB Output is correct
5 Correct 212 ms 26704 KB Output is correct
6 Correct 77 ms 15576 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5330 ms 237556 KB Output is correct
2 Correct 5494 ms 237400 KB Output is correct
3 Correct 4912 ms 236864 KB Output is correct
4 Correct 1860 ms 133968 KB Output is correct
5 Correct 3550 ms 125536 KB Output is correct
6 Correct 600 ms 63648 KB Output is correct
7 Correct 112 ms 17368 KB Output is correct