oj.uz

Submission #679664

# Submission time Handle Problem Language Result Execution time Memory
679664 2023-01-08T20:29:43 Z peijar Cities (BOI16_cities) C++17
100 / 100
 5586 ms 180684 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 : seen[u])
      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]);
      }
    seen[u].push_back(msk);
    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 1 ms 2644 KB Output is correct
3 Correct 1 ms 2644 KB Output is correct
4 Correct 1 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 729 ms 72776 KB Output is correct
2 Correct 767 ms 61648 KB Output is correct
3 Correct 124 ms 38912 KB Output is correct
4 Correct 66 ms 12696 KB Output is correct
5 Correct 322 ms 48572 KB Output is correct
6 Correct 53 ms 12264 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 3560 KB Output is correct
2 Correct 8 ms 3572 KB Output is correct
3 Correct 5 ms 3284 KB Output is correct
4 Correct 5 ms 3376 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2281 ms 102344 KB Output is correct
2 Correct 1923 ms 100588 KB Output is correct
3 Correct 1069 ms 70972 KB Output is correct
4 Correct 1393 ms 62240 KB Output is correct
5 Correct 262 ms 28324 KB Output is correct
6 Correct 81 ms 15572 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5471 ms 173672 KB Output is correct
2 Correct 5586 ms 180684 KB Output is correct
3 Correct 4902 ms 171768 KB Output is correct
4 Correct 2307 ms 161480 KB Output is correct
5 Correct 3532 ms 108932 KB Output is correct
6 Correct 592 ms 37300 KB Output is correct
7 Correct 113 ms 19264 KB Output is correct