fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN=1e5+5, INF=1e18;
  5.  
  6. long long n,L,R,X,u,v;
  7. long long a[MaxN],d[MaxN];
  8. vector<long long> b;
  9. vector<long long> vt[MaxN];
  10. bool used[MaxN];
  11.  
  12. long long get_id(long long x)
  13. {
  14.     return lower_bound(b.begin(),b.end(),x)-b.begin()+1;
  15. }
  16.  
  17. void dijkstra()
  18. {
  19.     priority_queue<pair<long long,long long>,
  20.                    vector<pair<long long,long long>>,
  21.                    greater<pair<long long,long long>>> pq;
  22.  
  23.     d[u]=0;
  24.     pq.push({0,u});
  25.  
  26.     while(!pq.empty())
  27.     {
  28.         long long du=pq.top().first;
  29.         long long x=pq.top().second;
  30.         pq.pop();
  31.  
  32.         if(du!=d[x])
  33.             continue;
  34.  
  35.         if(x-1>=1)
  36.         {
  37.             if(d[x-1]>du+L)
  38.             {
  39.                 d[x-1]=du+L;
  40.                 pq.push({d[x-1],x-1});
  41.             }
  42.         }
  43.  
  44.         if(x+1<=n)
  45.         {
  46.             if(d[x+1]>du+R)
  47.             {
  48.                 d[x+1]=du+R;
  49.                 pq.push({d[x+1],x+1});
  50.             }
  51.         }
  52.  
  53.         long long id=get_id(a[x]);
  54.  
  55.         if(used[id]==0)
  56.         {
  57.             used[id]=1;
  58.  
  59.             for(auto y:vt[id])
  60.             {
  61.                 if(d[y]>du+X)
  62.                 {
  63.                     d[y]=du+X;
  64.                     pq.push({d[y],y});
  65.                 }
  66.             }
  67.         }
  68.     }
  69. }
  70.  
  71. void input()
  72. {
  73.     cin>>n>>L>>R>>X>>u>>v;
  74.  
  75.     for(long long i=1;i<=n;i++)
  76.     {
  77.         cin>>a[i];
  78.         b.push_back(a[i]);
  79.     }
  80.  
  81.     sort(b.begin(),b.end());
  82.  
  83.     b.erase(unique(b.begin(),b.end()),b.end());
  84.  
  85.     for(long long i=1;i<=n;i++)
  86.     {
  87.         long long id=get_id(a[i]);
  88.         vt[id].push_back(i);
  89.     }
  90. }
  91.  
  92. void output()
  93. {
  94.     for(long long i=1;i<=n;i++)
  95.         d[i]=INF;
  96.  
  97.     dijkstra();
  98.  
  99.     cout<<d[v];
  100. }
  101.  
  102. int main()
  103. {
  104.     ios_base::sync_with_stdio(0);
  105.     cin.tie(0);
  106.  
  107.     input();
  108.     output();
  109. }
  110.  
Success #stdin #stdout 0.01s 7292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DiGGDs
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!