Submission #679665

#	Time	Username	Problem	Language	Result	Execution time	Memory
679665		peijar	Cities (BOI16_cities)	C++17	100 / 100	5494 ms	237556 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26