Cod sursă (job #466234)

#include <bits/stdc++.h>

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(){
//    ifstream cin("evacuare.in");
//  ofstream cout("evacuare.out");

    cin>>n>>m>>x);

    for(int i=1; i<=m; ++i)
    {
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=1; i<=n; ++i)
        cin>>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;
        for(int i=1; i<=l1; ++i)
        {
            nod=q1[i];
            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)
        cout<<sol[i];

    return 0;
}