2015年3月23日 星期一

2015/03/23 POI 20th Price List

/*
    一道容易想錯
    且複雜度不好估的題目
*/
// http://main.edu.pl/en/archive/oi/20/cen
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define INF 2000000000
typedef long long ll;

int dis[200000];
queue<int> que;

vector<int> v[200000];
vector<int> r[200000];

int N, M, K, A, B;

bool ban[200000];

ll Ans[200000];

int main()
{
    scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);

    for(int Ni = 1; Ni <= N; Ni++)
        Ans[Ni] = INF, dis[Ni] = INF;

    for(int Mi = 0; Mi < M; Mi++)
    {
        int x, y;
        scanf("%d %d", &x, &y);

        v[x].push_back(y);
        v[y].push_back(x);

        r[x].push_back(y);
        r[y].push_back(x);
    }

    dis[K] = 0;
    que.push(K);

    while( !que.empty() )
    {
        int F = que.front();
        que.pop();

        for(int vi = 0; vi < v[F].size(); vi++)
        {
            if( dis[v[F][vi] ] > dis[F]+1 )
            {
                dis[v[F][vi] ] = dis[F]+1;
                que.push(v[F][vi] );
            }
        }
    }

    for(int Ni = 1; Ni <= N; Ni++)
        Ans[Ni] = min(Ans[Ni], (ll)dis[Ni]*A), dis[Ni] = INF;

    dis[K] = 0;
    que.push(K);

    while( !que.empty() )
    {
        int F = que.front();
        que.pop();

        for(int vi = 0; vi < v[F].size(); vi++)
            ban[v[F][vi] ] = true;

        for(int vi = 0; vi < v[F].size(); vi++)
        {
            int t = v[F][vi];
            vector<int> p;

            for(int ri = 0; ri < r[t].size(); ri++)
            {
                if( ban[r[t][ri] ] )
                    p.push_back(r[t][ri] );
                else
                {
                    if( dis[r[t][ri] ] > dis[F]+1 )
                    {
                        dis[r[t][ri] ] = dis[F]+1;
                        que.push(r[t][ri] );
                    }
                }
            }

            r[t] = p;
        }

        for(int vi = 0; vi < v[F].size(); vi++)
            ban[v[F][vi] ] = false;
    }

    for(int Ni = 1; Ni <= N; Ni++)
        Ans[Ni] = min(Ans[Ni], (ll)dis[Ni]*B);

    for(int Ni = 1; Ni <= N; Ni++)
    {
        for(int vi = 0; vi < v[Ni].size(); vi++)
            Ans[Ni] = min(Ans[Ni], Ans[v[Ni][vi] ]+A);

        printf("%lld\n", Ans[Ni]);
    }
}

沒有留言:

張貼留言