oj.uz

Submission #1082580

# Submission time Handle Problem Language Result Execution time Memory
1082580 2024-08-31T16:20:11 Z Wjsc Cities (BOI16_cities) C++14
100 / 100
 5782 ms 89260 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 12 ms 57948 KB Output is correct
2 Correct 11 ms 57852 KB Output is correct
3 Correct 11 ms 57948 KB Output is correct
4 Correct 11 ms 58064 KB Output is correct
5 Correct 12 ms 57948 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 78240 KB Output is correct
2 Correct 949 ms 79592 KB Output is correct
3 Correct 400 ms 68764 KB Output is correct
4 Correct 63 ms 67676 KB Output is correct
5 Correct 389 ms 78168 KB Output is correct
6 Correct 50 ms 67272 KB Output is correct
7 Correct 16 ms 58200 KB Output is correct
8 Correct 11 ms 58068 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 58216 KB Output is correct
2 Correct 20 ms 58200 KB Output is correct
3 Correct 18 ms 58208 KB Output is correct
4 Correct 16 ms 58152 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2271 ms 78936 KB Output is correct
2 Correct 2239 ms 87120 KB Output is correct
3 Correct 1298 ms 68288 KB Output is correct
4 Correct 1022 ms 78396 KB Output is correct
5 Correct 259 ms 73224 KB Output is correct
6 Correct 74 ms 70244 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5017 ms 80680 KB Output is correct
2 Correct 5447 ms 80680 KB Output is correct
3 Correct 5782 ms 89260 KB Output is correct
4 Correct 3061 ms 68764 KB Output is correct
5 Correct 2490 ms 79004 KB Output is correct
6 Correct 669 ms 76300 KB Output is correct
7 Correct 125 ms 70884 KB Output is correct