fork download
copy 
  1. #include<cstdio>
  2. #include<cstdlib>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<fstream>
  7. #include<map>
  8. #include<ctime>
  9. #include<set>
  10. #include<queue>
  11. #include<cmath>
  12. #include<vector>
  13. #include<bitset>
  14. #include<functional>
  15. #define x first
  16. #define y second
  17. #define mp make_pair
  18. #define pb push_back
  19. #define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
  20. #define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
  21. using namespace std;
  22.  
  23. typedef long long LL;
  24. typedef double ld;
  25.  
  26. const int MAX=400000+10;
  27.  
  28. int i;
  29. int n,m,K,A,B;
  30.  
  31. int begin[MAX],next[MAX],t[MAX],tot;
  32. int begin2[MAX];
  33.  
  34. void add(int begin[MAX],int a,int b)
  35. {
  36.     t[++tot]=b;
  37.     next[tot]=begin[a];
  38.     begin[a]=tot;
  39. }
  40.  
  41. int q[MAX],dist[MAX];
  42.  
  43. void BFS(int S)
  44. {
  45.     int i;
  46.     REP(i,1,n)
  47.         dist[i]=-1;
  48.     dist[S]=0;
  49.     int head=0,end=0;
  50.     q[end++]=S;
  51.     while(head<end)
  52.     {
  53.         int u=q[head++];
  54.         for(i=begin[u];i;i=next[i])
  55.         {
  56.             int v=t[i];
  57.             if(dist[v]==-1)
  58.             {
  59.                 dist[v]=dist[u]+1;
  60.                 q[end++]=v;
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. int dist2[MAX],is[MAX];
  67. int hash[MAX];
  68.  
  69. void BFS2(int u)
  70. {
  71.     int i;
  72.     REP(i,1,n)
  73.         dist2[i]=-1;
  74.     int head=0,end=0;
  75.     q[end++]=u;
  76.     dist2[u]=0;
  77.     while(head<end)
  78.     {
  79.         int u=q[head++];
  80.         for(i=begin[u];i;i=next[i])
  81.             is[t[i]]=u;
  82.         for(i=begin[u];i;i=next[i])
  83.         {
  84.             int v=t[i];
  85.             int* last=begin2+v;
  86.             for(int j=begin2[v];j;j=next[j])
  87.             {
  88.                 int p=t[j];
  89.                 if(is[p]!=u)
  90.                 {
  91.                     if(dist2[p]==-1)
  92.                     {
  93.                         dist2[p]=dist2[u]+1;
  94.                         q[end++]=p;
  95.                     }
  96.                 }
  97.                 else
  98.                 {
  99.                     *last=j;
  100.                     last=next+j;
  101.                 }
  102.             }
  103.             *last=0;
  104.         }
  105.     }
  106. }
  107.  
  108. int main()
  109. {
  110. //    freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
  111.     int i;
  112.     cin>>n>>m>>K>>A>>B;
  113.     REP(i,1,m)
  114.     {
  115.         int a,b;
  116.         scanf("%d%d",&a,&b);
  117.         add(begin,a,b);
  118.         add(begin,b,a);
  119.         add(begin2,a,b);
  120.         add(begin2,b,a);
  121.     }
  122.     BFS(K);
  123.     BFS2(K);
  124.     REP(i,1,n)
  125.     {
  126.         int ans=min(dist[i]*A,(dist[i]/2)*B + (dist[i]%2)*A);
  127.         if(dist2[i]!=-1)
  128.             ans=min(ans,dist2[i]*B);
  129.         printf("%d\n",ans);
  130.     }
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0s 17408KB
comments (?)
stdin
copy 
5 5 1 3 2
1 2
2 3
3 4
4 5
3 1
stdout
copy 
0
3
3
2
5
https://ideone.com/C8kVvt
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!