Submission #258310

#	Time	Username	Problem	Language	Result	Execution time	Memory
258310		rama_pang	Cities (BOI16_cities)	C++14	100 / 100	2616 ms	73956 KiB

cities

#include <bits/stdc++.h>
using namespace std;

using lint = long long;

struct State {
  int u, mask;
  lint d;
  State() {}
  State(int u, int mask, lint d) : u(u), mask(mask), d(d) {}
  bool operator < (const State &o) const {
    return d > o.d || (d == o.d && mask > o.mask); // for pq
  }
};

lint dist[100005][1 << 4];
vector<pair<int, int>> radj[100005];
priority_queue<State> pq;

lint Solve(int N, int K, int M, vector<int> special, vector<vector<pair<int, int>>> adj) {
  for (int i = 0; i < N; i++) {
    for (auto j : adj[i]) if (j.first != -1) {
      radj[j.first].emplace_back(i, j.second);
    }
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < (1 << (K - 1)); j++) {
      dist[i][j] = 1e18;
    }
  }

  auto Relax = [&](int u, int mask, lint d) {
    if (dist[u][mask] > d) {
      dist[u][mask] = d;
      pq.emplace(u, mask, d);
    }
  };
  vector<int> specialid(N, -1);
  for (int i = 0; i < (K - 1); i++) {
    specialid[special[i]] = i;
    Relax(i, 0, 0);
  }
  for (int i = 0; i < N; i++) {
    Relax(i, 0, 0);
  }
  while (!pq.empty()) {
    State s = pq.top();
    pq.pop();
    if (dist[s.u][s.mask] != s.d) {
      continue;
    }
    if (specialid[s.u] != -1) {
      Relax(s.u, s.mask | (1 << specialid[s.u]), dist[s.u][s.mask]);
    }
    int othermask = ((1 << (K - 1)) - 1) ^ s.mask;
    for (int m = othermask; m > 0; m = (m - 1) & othermask) {
      Relax(s.u, s.mask | m, dist[s.u][s.mask] + dist[s.u][m]);
    }      
    for (auto v : radj[s.u]) {
      Relax(v.first, s.mask, s.d + v.second);
    }
  }
  return dist[special.back()][(1 << (K - 1)) - 1];
}

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

  int N, K, M;
  cin >> N >> K >> M;

  vector<int> special(K);
  for (int i = 0; i < K; i++) {
    cin >> special[i];
    special[i]--;
  }

  vector<vector<pair<int, int>>> edgelist(N);
  for (int i = 0; i < M; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    edgelist[u].emplace_back(v, w);
    edgelist[v].emplace_back(u, w);
  }

  cout << Solve(N, K, M, special, edgelist) << "\n";
  return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26