Anime Shops

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

#define MAXN 100000
#define INF 1e6

typedef pair<int, int> pii;
priority_queue<pii> q;
vector<int> adj[MAXN];
int dist[MAXN];
int parent[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m, k;
  cin >> n >> m >> k;

  vector<bool> shop(n, false);

  int c;
  for (int i = 0; i < k; ++i) {
    cin >> c;
    shop[c] = true;
  }

  int a, b;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b;

    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }

  for (int x = 1; x < n + 1; ++x) {
    fill_n(dist, n, 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]) {
          parent[b] = a;
          dist[b] = dist[a] + 1;
          q.push({-dist[b], b});
        }
      }
    }

    cout << (target == -1 ? target : dist[target]) << ' ';
  }
}

Test 1

Group: 1, 3

Verdict: ACCEPTED

Test 2

Group: 1, 3

Verdict: WRONG ANSWER

Test 3

Group: 1, 3

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 10

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 3

Verdict: TIME LIMIT EXCEEDED