oj.uz

Submission #391073

# Submission time Handle Problem Language Result Execution time Memory
391073 2021-04-17T19:16:02 Z Hegdahl Cities (BOI16_cities) C++17
100 / 100
 3032 ms 46400 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ar array

using namespace std;
using ll = long long;

const ll INF = 1LL<<60;
const int mxN = 1e5;

vector<ar<int, 2>> g[mxN];

ll cost[1<<5][mxN];

void dijkstra(int start, vector<ll> &dists) {
  priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
  pq.push({0, start});

  vector<bool> vis(dists.size());
  while (pq.size()) {
    auto [dhere, cur] = pq.top();
    pq.pop();

    if (vis[cur]) continue;
    dists[cur] = dhere;
    vis[cur] = true;

    //cerr << cur << ' ' << dhere << ' ' << vis_cnt << '\n';

    for (auto [nxt, w] : g[cur]) {
      if (dhere+w >= dists[nxt]) continue;
      dists[nxt] = dhere+w;
      pq.push({dhere+w, nxt});
    }
  }

  for (ll x : dists)
    assert(x != -1);
}

vector<ll> dists[5];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);

  int n, k, m; cin >> n >> k >> m;

  vector<int> special(k);
  for (int &x : special) cin >> x, --x;

  vector<ar<int, 3>> e(m);
  for (auto &[i, j, w] : e) {
    cin >> i >> j >> w; --i, --j;
    g[i].push_back({j, w});
    g[j].push_back({i, w});
  }

  //cerr << "starting dijkstras\n";

  for (int kk = 0; kk < k; ++kk) {
    //cerr << kk << '\n';
    dists[kk].resize(n, INF);
    dijkstra(special[kk], dists[kk]);
  } // */

  for (int s = 0; s < 1<<k; ++s)
    for (int i = 0; i < n; ++i)
      for (int kk = 0; kk < k; ++kk)
        if (s&(1<<kk))
          cost[s][i] += dists[kk][i];

  /*
  for (int s = 0; s < 1<<k; ++s) {
    cerr << bitset<5>(s) << '\n';
    for (int i = 0; i < n; ++i)
      cerr << cost[s][i] << " \n"[i==n-1];
  } // */

  vector<bool> vis(n);
  priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;

  for (int cnt = 2; cnt <= k; ++cnt) {
    cerr << cnt << '\n';
    for (int s1 = 1; s1 < 1<<k; ++s1) {
      for (int s2 = s1+1; s2 < 1<<k; ++s2) {
        if (s1&s2) continue;
        int s3 = s1|s2;
        if (__builtin_popcount(s3) != cnt) continue;

        for (int i = 0; i < n; ++i) {
          ll min1 = cost[s1][i], min2 = cost[s2][i];
          for (auto [j, w] : g[i]) {
            if (min1 > cost[s1][j]+w)
              min1 = cost[s1][j]+w;
            if (min2 > cost[s2][j]+w)
              min2 = cost[s2][j]+w;
          }
          if (cost[s3][i] > min1+min2)
            cost[s3][i] = min1+min2;
        }
      }
    }

    //cerr << "combined\n";

    for (int s = 0; s < 1<<k; ++s) {
      if (__builtin_popcount(s) != cnt) continue;
      //cerr << bitset<5>(s) << '\n';

      for (int i = 0; i < n; ++i)
        pq.push({cost[s][i], i});

      fill(vis.begin(), vis.end(), 0);
      while (pq.size()) {
        auto [dhere, cur] = pq.top();
        pq.pop();

        if (vis[cur]) continue;
        vis[cur] = 1;

        for (auto [nxt, w] : g[cur]) {
          if (dhere+w >= cost[s][nxt]) continue;
          cost[s][nxt] = dhere+w;
          pq.push({dhere+w, nxt});
        }
      }
    }
  }

  int all = 1<<k;
  ll ans = INF;
  for (int i = 0; i < n; ++i)
    if (ans > cost[all-1][i])
      ans = cost[all-1][i];

  cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct
3 Correct 3 ms 2636 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 23416 KB Output is correct
2 Correct 600 ms 26040 KB Output is correct
3 Correct 344 ms 18272 KB Output is correct
4 Correct 78 ms 10976 KB Output is correct
5 Correct 331 ms 20608 KB Output is correct
6 Correct 70 ms 10900 KB Output is correct
7 Correct 6 ms 2892 KB Output is correct
8 Correct 4 ms 2892 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3000 KB Output is correct
2 Correct 10 ms 3020 KB Output is correct
3 Correct 6 ms 2892 KB Output is correct
4 Correct 6 ms 2892 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1293 ms 30444 KB Output is correct
2 Correct 1287 ms 33152 KB Output is correct
3 Correct 727 ms 25236 KB Output is correct
4 Correct 715 ms 22548 KB Output is correct
5 Correct 201 ms 13392 KB Output is correct
6 Correct 101 ms 12848 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2957 ms 43828 KB Output is correct
2 Correct 3032 ms 45032 KB Output is correct
3 Correct 2742 ms 46400 KB Output is correct
4 Correct 1729 ms 38644 KB Output is correct
5 Correct 1538 ms 29372 KB Output is correct
6 Correct 368 ms 14716 KB Output is correct
7 Correct 174 ms 12864 KB Output is correct