Cod sursă (job #431400)

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int DIM = (1 << 17);

// ez pz dinamica pe graf
int n, m, x, a, b;

int dp[500005], p[500005];
vector <int> g[500005];
queue <int> q;

char next_char() {
  static char buff[DIM];
  static int bp = DIM;
  if(bp == DIM) {
    fread(buff, 1, DIM, stdin);
    bp = 0;
  }
  return buff[bp++];
}

void read(int &x) {
  static char ch;
  do {
    ch = next_char();
  } while(ch < '0' || '9' < ch);
  x = 0;
  do {
    x = x * 10 + ch - '0';
    ch = next_char();
  } while('0' <= ch && ch <= '9');
}

int main() {
  freopen("evacuare.in", "r", stdin);
  freopen("evacuare.out", "w", stdout);
  read(n); read(m); read(x);
  for(; m; m--) {
    read(a); read(b);
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for(int i = 1; i <= n; i++) {
    read(p[i]);
    dp[i] = 1e9;
  }
  dp[x] = 1;
  q.push(x);
  while(!q.empty()) {
    x = q.front();
    q.pop();
    for(auto i : g[x]) {
      int c = dp[x] + (p[x] != i);
      if(dp[i] > c) {
        dp[i] = c;
        q.push(i);
      }
    }
  }
  for(int i = 1; i <= n; i++)
    printf("%d\n", dp[i] - 1);
  return 0;
}