oj.uz

Submission #1082579

# Submission time Handle Problem Language Result Execution time Memory
1082579 2024-08-31T16:18:39 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 5719 ms 93492 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
#define pi pair<int, int>
#define fi first
#define se second
#define all(v) v.begin(), v.end()

const int N = 1e5 + 5,
          INF = 1e17;

int n, k, m;
int b[N];
int f[N][70];
vector<pi> ad[N];

void Dij(int st) { // st - mask
  using tp = tuple<int, int, int>;
  priority_queue<tp, vector<tp>, greater<tp>> q;

  for(int i = 1; i <= n; ++i) q.emplace(f[i][st], i, st);

  while(q.size()) {
    int c, u, mask; tie(c, u, mask) = q.top();
    q.pop();

    if(f[u][mask] < c) continue;

    for(auto x : ad[u]) {
      int v, w; tie(v, w) = x;
      int nMask = mask | b[v];
      if(f[v][nMask] > c + w) f[v][nMask] = c + w, q.emplace(f[v][nMask], v, nMask);
    }
  }
}

signed main() {
  cin.tie(0)->sync_with_stdio(0);

  if(fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  cin >> n >> k >> m;
  for(int i = 1, id = 0; i <= k; ++i) {
    int x; cin >> x;
    b[x] = (1 << id++);
  }

  for(int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    ad[u].emplace_back(v, w);
    ad[v].emplace_back(u, w);
  }

  memset(f, 21, sizeof f);

  for(int i = 1; i <= n; ++i) f[i][b[i]] = 0;

  for(int mask = 0; mask < (1 << k); ++mask) {
    for(int sub1 = 0; sub1 < (1 << k); ++sub1) {
      int sub2 = mask ^ sub1;
      for(int i = 1; i <= n; ++i) f[i][mask] = min(f[i][mask], f[i][sub1] + f[i][sub2]);
    }
    Dij(mask);
  }

  int ans = INF;
  for(int i = 1; i <= n; ++i) ans = min(ans, f[i][(1 << k) - 1]);
  cout << ans;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:44:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 57948 KB Output is correct
2 Correct 11 ms 57948 KB Output is correct
3 Correct 12 ms 57948 KB Output is correct
4 Correct 11 ms 57948 KB Output is correct
5 Correct 11 ms 58044 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 82344 KB Output is correct
2 Correct 944 ms 83796 KB Output is correct
3 Correct 402 ms 70876 KB Output is correct
4 Correct 68 ms 71256 KB Output is correct
5 Correct 398 ms 82444 KB Output is correct
6 Correct 50 ms 70688 KB Output is correct
7 Correct 14 ms 58204 KB Output is correct
8 Correct 11 ms 58256 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 58196 KB Output is correct
2 Correct 21 ms 58364 KB Output is correct
3 Correct 16 ms 58204 KB Output is correct
4 Correct 16 ms 58204 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2170 ms 83124 KB Output is correct
2 Correct 2253 ms 91408 KB Output is correct
3 Correct 1277 ms 70412 KB Output is correct
4 Correct 1032 ms 82664 KB Output is correct
5 Correct 245 ms 76940 KB Output is correct
6 Correct 75 ms 73828 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5141 ms 84956 KB Output is correct
2 Correct 5562 ms 84980 KB Output is correct
3 Correct 5719 ms 93492 KB Output is correct
4 Correct 3112 ms 70876 KB Output is correct
5 Correct 2607 ms 83184 KB Output is correct
6 Correct 683 ms 80304 KB Output is correct
7 Correct 136 ms 74212 KB Output is correct