제출 #391073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391073		Hegdahl	Cities (BOI16_cities)	C++17	100 / 100	3032 ms	46400 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26