Submission #1123970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123970		fryingduc	Cities (BOI16_cities)	C++20	74 / 100	6095 ms	169416 KiB

cities

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 1e5 + 5;
int n, m, k;
vector<pair<int, int>> g[maxn];
int is_spec[maxn];
int spec[maxn];

const int MASK = (1 << 5) + 5;
struct info {
  long long dist;
  int mask;
  int u;
  
  bool operator<(const info &o) const {
    return dist < o.dist;
  } 
  bool operator>(const info &o) const {
    return dist > o.dist;
  }
};
long long d[maxn][MASK];
void solve() {
  cin >> n >> k >> m;
  for(int i = 1; i <= k; ++i) {
    cin >> spec[i];
    is_spec[spec[i]] = i;
  }
  for(int i = 1; i <= m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  priority_queue<info, vector<info>, greater<info>> pq;
  memset(d, 0x3f, sizeof(d));
  for(int i = 1; i <= n; ++i) {
    d[i][0] = 0;
  }
  for(int i = 1; i <= n; ++i) {
    int mask = (is_spec[i] ? (1 << (is_spec[i] - 1)) : 0);
    pq.push({0, mask, i});
    d[i][mask] = 0;
  }
  while(!pq.empty()) {
    long long dist = pq.top().dist;
    int mask = pq.top().mask;
    int u = pq.top().u;
    pq.pop();
    if(dist > d[u][mask]) continue;
//    debug(u, mask, dist);
    for(auto e:g[u]) {
      int v = e.first, w = e.second;
      for(int i = 0; i < (1 << k); ++i) {
        int new_mask = i | mask;
        if(is_spec[v]) {
          new_mask |= (1 << (is_spec[v] - 1));
        }
        long long cost = dist + w + d[v][i];
        if(cost < d[v][new_mask]) {
          d[v][new_mask] = cost;
          pq.push({cost, new_mask, v});
        }
      }
    }
  }
  long long res = 1e18;
  for(int i = 1; i <= n; ++i) {
    res = min(res, d[i][(1 << k) - 1]);
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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