Cod sursă (job #431375)

#include <cstdio>
#include <vector>

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];

void dfs(int nod) {
  for(auto i : g[nod]) {
    int c = dp[nod] + (p[nod] != i);
    if(dp[i] > c) {
      dp[i] = c;
      dfs(i);
    }
  }
}

char next_char() {
  static char buff[DIM];
  static int bp = 0;
  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;
  dfs(x);
  for(int i = 1; i <= n; i++)
    printf("%d\n", dp[i] - 1);
  return 0;
}