Từ Trường THPT chuyên Lương Văn Tụy, Ninh Bình
Thông tin
include <bits/stdc++.h>
define ii pair<int,int>
define ll long long
using namespace std; const long long N=1e6+5,INF=1e18; vector<pair<ll,ll>> adj[N]; vector<int> kk[N]; long long d[N],d2[N],n,m,l,r,c,h,k,mx=-1,a[N]; void file() { freopen("KTKS.inp","r",stdin); freopen("KTKS.out","w",stdout); } void dij(int u) { for(int i=1;i<=n;i++) d[i]=INF; priorityqueue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> q; d[u]=0; q.push({0,u}); while(!q.empty()) { ii top=q.top(); q.pop(); ll du=top.first; ll x=top.second; if(du!=d[x]) continue; for(auto [v,w]:adj[x]) { if(d[v]>w+d[x]) { d[v]=d[x]+w; q.push({d[v],v}); } } for(auto v:kk[a[x]]) { if(v!=x) { if(d[v]>c+d[x]) { d[v]=d[x]+c; q.push({d[v],v}); } } } } } int main() { //file(); iosbase::syncwithstdio(false); cin.tie(nullptr), cout.tie(nullptr); cin>>n>>l>>r>>c; cin>>h>>k; for(int i=1;i<=n;i++) { cin>>a[i]; mx=max(mx,a[i]); kk[a[i]].pushback(i); } adj[1].pushback({2,r}); adj[n].pushback({n-1,l}); for(int i=2;i<n;i++) { adj[i].pushback({i+1,r}); adj[i].push_back({i-1,l}); } dij(h); cout<<d[k];
}