Cod sursă (job #143319)

#include <cstdio>
#include <vector>

using namespace std;

#define maxn 500010
#define inf 1000000000

int n, m, a, b, x, nod, fiu;
char f[maxn];
int p[maxn], sol[maxn];
int l1, l2, q1[maxn], q2[maxn];
vector<int> v[maxn];

int main()
{
    freopen("evacuare.in", "r", stdin);
    freopen("evacuare.out", "w", stdout);

    scanf("%d%d%d", &n, &m, &x);

    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; ++i)
        scanf("%d", &p[i]);

    for(int i=1; i<=n; ++i)
        sol[i]=inf;

    sol[x]=0;
    l1=1;
    q1[1]=x;

    while(l1>0)
    {
        l2=0;
    //    printf("*");
        for(int i=1; i<=l1; ++i)
        {
            nod=q1[i];
           // printf("%d %d %d\n", nod, p[nod], sol[nod]);

            if(f[nod])
                continue;
            f[nod]=1;

            for(int j=0; j<v[nod].size(); ++j)
            {
                fiu=v[nod][j];

                if(f[fiu])
                    continue;

                if(fiu==p[nod])
                {
                    if(sol[nod]<sol[fiu])
                    {
                        sol[fiu]=sol[nod];
                        q1[++l1]=fiu;
                    }
                }
                else
                {
                    if(sol[nod]+1<sol[fiu])
                    {
                        sol[fiu]=sol[nod]+1;
                        q2[++l2]=fiu;
                    }
                }
            }
        }
        l1=l2;
        for(int i=1; i<=l1; ++i)
            q1[i]=q2[i];
    }

    for(int i=1; i<=n; ++i)
        printf("%d\n", sol[i]);

    return 0;
}