Cod sursă (job #143321)

#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];
vector<pair<int, int> > h;

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);
    }

    h.push_back(make_pair(0, x));
    for(int i=1; i<=n; ++i)
        d[i]=inf;
    d[x]=0;

    while(h.size()>0)
    {
        nod=h[0].second;
        pop_heap(h.begin(), h.end());
        h.pop_back();

        if(f[nod])
            continue;

        f[nod]=1;

        for(int i=0; i<v[nod].size(); ++i)
        {
            fiu=v[nod][i];
            if(d[nod]+w[nod][i]<d[fiu])
            {
                d[fiu]=d[nod]+w[nod][i];
                h.push_back(make_pair(-d[fiu], fiu));
                push_heap(h.begin(), h.end());
            }
        }
    }

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

    return 0;
}