Submission #798013

#	Time	Username	Problem	Language	Result	Execution time	Memory
798013		tch1cherin	Cities (BOI16_cities)	C++17	100 / 100	3107 ms	48712 KiB

cities

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
const int64_t INF = 2e18;
vector<pair<int, int>> G[MAX_N];

int64_t _min(int64_t a, int64_t b) { return a < b ? a : b; }

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, K, M;
  cin >> N >> K >> M;
  vector<int> S(K);
  for (int &v : S) {
    cin >> v;
    v--;
  }
  for (int i = 0; i < M; i++) {
    int A, B, C;
    cin >> A >> B >> C;
    A--, B--;
    G[A].push_back({B, C});
    G[B].push_back({A, C});
  }
  vector<vector<int64_t>> DP(N, vector<int64_t>(1 << K, INF));
  for (int i = 0; i < K; i++) {
    DP[S[i]][1 << i] = 0;
  }
  for (int mask = 1; mask < (1 << K); mask++) {
    for (int i = 0; i < N; i++) {
      for (int submask = mask; submask * 2 >= mask; submask = (submask - 1) & mask) {
        DP[i][mask] = _min(DP[i][mask], DP[i][submask] + DP[i][mask ^ submask]);
      }
    }
    auto cmp = [&](pair<int64_t, int> a, pair<int64_t, int> b) { return a.first > b.first; };
    priority_queue<pair<int64_t, int>, vector<pair<int64_t, int>>, decltype(cmp)> q(cmp);
    for (int i = 0; i < N; i++) {
      if (DP[i][mask] != INF) {
        q.push({DP[i][mask], i});
      }
    }
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      if (d == DP[u][mask]) {
        for (auto [v, w] : G[u]) {
          if (DP[u][mask] + w < DP[v][mask]) {
            q.push({DP[v][mask] = DP[u][mask] + w, v});
          }
        }
      }
    }
  }
  int64_t ans = INF;
  for (int i = 0; i < N; i++) {
    ans = min(ans, DP[i].back());
  }
  cout << ans << "\n";
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26