oj.uz

Submission #798013

# Submission time Handle Problem Language Result Execution time Memory
798013 2023-07-30T09:08:49 Z tch1cherin Cities (BOI16_cities) C++17
100 / 100
 3107 ms 48712 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 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 616 ms 29616 KB Output is correct
2 Correct 624 ms 29656 KB Output is correct
3 Correct 346 ms 21680 KB Output is correct
4 Correct 47 ms 10820 KB Output is correct
5 Correct 251 ms 24344 KB Output is correct
6 Correct 53 ms 10788 KB Output is correct
7 Correct 4 ms 2900 KB Output is correct
8 Correct 3 ms 2808 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2988 KB Output is correct
2 Correct 6 ms 2900 KB Output is correct
3 Correct 5 ms 2844 KB Output is correct
4 Correct 4 ms 2812 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1390 ms 36008 KB Output is correct
2 Correct 1460 ms 35864 KB Output is correct
3 Correct 926 ms 27988 KB Output is correct
4 Correct 721 ms 24276 KB Output is correct
5 Correct 138 ms 13644 KB Output is correct
6 Correct 57 ms 12364 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2939 ms 48592 KB Output is correct
2 Correct 3107 ms 48712 KB Output is correct
3 Correct 2838 ms 48372 KB Output is correct
4 Correct 1847 ms 40608 KB Output is correct
5 Correct 1271 ms 30612 KB Output is correct
6 Correct 258 ms 15108 KB Output is correct
7 Correct 70 ms 12452 KB Output is correct