Cod sursă (job #143320)

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define maxn 500010
#define inf 1000000000

int n, m, a, b, x, nod, fiu, p[maxn], d[maxn], f[maxn];
vector<int> v[maxn], w[maxn];
int q0, q[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);
        w[a].push_back(1);
        w[b].push_back(1);
    }
    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &p[i]);
        v[i].push_back(p[i]);
        w[i].push_back(0);
    }

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

    d[x]=0;
    f[x]=1;
    q[++q0]=x;

    int nod, fiu;

    for(int i=1; i<=q0; ++i)
    {
        nod=q[i%maxn];
        f[nod]=0;
        for(int j=0; j<v[nod].size(); ++j)
        {
            fiu=v[nod][j];
            if(d[nod]+w[nod][j]<d[fiu])
            {
                d[fiu]=d[nod]+w[nod][j];
                if(f[fiu]==0)
                {
                    f[fiu]=1;
                    ++q0;
                    q[q0%maxn]=fiu;
                }
            }
        }
    }


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

    return 0;
}