[POI] 20th stage I - pA Price List

#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
using namespace std;
#define N 100005
vector<int> s[N],r[N],test;
int dis1[N],dis2[N],pre[N]={0},vi[N][2]={0},last[N]={0};
struct P{
    int x,y;
}in,out;
queue<P> que;
int main(){
    int n,m,k,a,b,x,y,i,j,ans;
    scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
    for(i=0;i<m;i++){
        scanf("%d%d",&x,&y);
        s[x].push_back(y);
        s[y].push_back(x);
        r[x].push_back(y);
        r[y].push_back(x);
    }
    memset(dis1,-1,sizeof(dis1));
    memset(dis2,-1,sizeof(dis2));
    que.push((P){k,0});
    dis1[k]=0;
    while(que.size()){
        out=que.front();
        que.pop();
        for(i=0;i<s[out.x].size();i++){
            int u=s[out.x][i];
            in.x=u;
            in.y=out.y+1;
            if(dis1[u]==-1){
                dis1[u]=in.y;
                que.push(in);
            }
        }
    }
    que.push((P){k,0});
    dis2[k]=0;
    while(que.size()){
        out=que.front();
        que.pop();
        int u=out.x;
        for(i=0;i<s[u].size();i++){
            int v=s[u][i];
            pre[v]=u;
        }
        for(i=0;i<s[u].size();i++){
            int v=s[u][i];
            test.clear();
            for(j=0;j<r[v].size();j++){
                int p=r[v][j];
                if(pre[p]!=u && dis2[p]==-1){
                    in.x=p;
                    in.y=out.y+1;
                    dis2[p]=in.y;
                    que.push(in);
                }
                else{
                    test.push_back(p);
                }
            }
            r[v]=test;
        }
    }
    for(i=1;i<=n;i++){
        ans=min(dis1[i]*a,dis1[i]/2*b+(dis1[i]%2)*a);
        if(dis2[i]>=0) ans=min(ans,dis2[i]*b);
        printf("%d\n",ans);
    }
}