Anime Shops

#include <bits/stdc++.h>
using namespace std;
 
#define MAXN 100001
#define INF 1e7
 
typedef pair<int, int> pii;
priority_queue<pii> q;
vector<int> adj[MAXN];
vector<int> dist;
vector<int> parent;
int srank[MAXN];
int n, m, k;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
 
  cin >> n >> m >> k;
 
  vector<bool> shop(n + 1, false);
 
  int c;
  for (int i = 0; i < k; ++i) {
    cin >> c;
    shop[c] = true;
  }
 
  parent.assign(n + 1, -1);
  fill_n(srank, n + 1, 1);
 
  int a, b;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;
 
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }
 
  // Group 2
  if (m == n - 1) {
    dist.assign(n + 1, INF);
    int seen = INF;
    for (int i = 1; i < n + 1; ++i) {
      dist[i] = seen + 1;
      if (shop[i]) {
        seen = 0;
      } else {
        seen++;
      }
    }
    seen = INF;
    for (int i = n; i > 0; --i) {
      dist[i] = min(seen + 1, dist[i]);
      if (shop[i]) {
        seen = 0;
      } else {
        seen++;
      }
    }
 
    for (int i = 1; i < n + 1; ++i) {
      cout << ((dist[i] < INF) ? dist[i] : -1) << ' ';
    }
    return 0;
  }
 
  for (int x = 1; x < n + 1; ++x) {
    dist.assign(n + 1, INF);
    dist[x] = 0;
 
    q = {};
    q.push({0, x});
 
    int target = -1;
 
    while (!q.empty()) {
      int a = q.top().second;
 
      // Found the shortest path to an anime shop
      if (shop[a] && a != x) {
        target = a;
 
        // printf("shortest %d -> %d dist: %d\n", x, a, dist[a]);
        break;
      }
 
      q.pop();
      for (auto &b : adj[a]) {
        if (dist[a] + 1 < dist[b]) {
          dist[b] = dist[a] + 1;
          q.push({-dist[b], b});
        }
      }
    }
 
    cout << (target == -1 ? target : dist[target]) << ' ';
  }
  cout << '\n';
}

Test 1

Group: 1, 3

Verdict: ACCEPTED

Test 2

Group: 1, 3

Verdict: ACCEPTED

Test 3

Group: 1, 3

Verdict: ACCEPTED

Test 4

Group: 1, 3

Verdict: ACCEPTED

Test 5

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 7

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2, 3

Verdict: ACCEPTED

Test 10

Group: 2, 3

Verdict: ACCEPTED

Test 11

Group: 2, 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED