Submission #1123972

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123972		fryingduc	Cities (BOI16_cities)	C++20	37 / 100	6098 ms	191360 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];
queue<pair<long long, int>> q[maxn];
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);
    q[mask].push({0, i});
    d[i][mask] = 0;
  }
  for(int mask = 0; mask < (1 << k); ++mask) {
    while(!q[mask].empty()) {
      int u = q[mask].front().second;
      long long dist = q[mask].front().first;
      q[mask].pop();
      if(dist > d[u][mask]) continue;
      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;
            q[new_mask].push({cost, 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: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26