BOJ 28283 - 해킹

BOJ 28283 - 해킹

모든 정점까지의 $B_i$ 에서 multi-source BFS를 돌려서 최단거리를 기록해두자.

도달할 수 없는데 $A_i > 0$ 이라면 정답은 $\infty$ 이다.

그렇지 않다면 $d_i \cdot A_i$ 가 큰 것 순서대로 $\text{Min}(X, n)$ 개 뽑아서 더해주면 정답이다.

void solve() {
   int n, m, x, y;
   cin >> n >> m >> x >> y;
   vi a(n);
   fv(a);
   vi dist(n, 2e18);
   vvi edges(n);
   for (int i = 0, u, v; i < m; i++) {
      cin >> u >> v, u--, v--, edges[u].pb(v), edges[v].pb(u);
   }
   queue<int> q;
   for (int i = 0; i < y; i++) {
      int k;
      cin >> k, k--;
      dist[k] = 0;
      q.push(k);
   }
   while (sz(q)) {
      int cur = q.front();
      q.pop();
      for (int to: edges[cur]) {
         if (dist[to] > dist[cur] + 1) {
            dist[to] = dist[cur] + 1;
            q.push(to);
         }
      }
   }
   vi costs;
   for (int i = 0; i < n; i++) {
      if (dist[i] == 2e18) {
         if (a[i] > 0) {
            cout << -1;
            return;
         }
      }
      int cost = dist[i] * a[i];
      costs.pb(cost);
   }
   sort(all(costs), greater<>());
   partial_sum(all(costs), costs.begin());
   cout << costs[min(n - 1, x - 1)];
}