fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> pii;
  4. int main() 
  5. {
  6. 	int n;
  7. 	cin>>n;
  8. 	int a[n];
  9. 	for(int i=0;i<n;i++)
  10. 	    cin>>a[i];
  11.     vector<pii> v[n+1];
  12.     for(int i=0;i<n;i++)
  13.     {
  14.         if(i==n-1)
  15.         {
  16.             v[i].push_back(make_pair(i+1,a[i]));
  17.             continue;
  18.         }
  19.  
  20.         if(i+2<=n)
  21.             v[i].push_back(make_pair(i+2,a[i]));
  22.         if(i-1>=0)
  23.             v[i].push_back(make_pair(i-1,a[i]));
  24.     }
  25.  
  26.     int vis[n+1];
  27.     memset(vis,0,sizeof(vis));
  28.  
  29.     int dist[n+1];
  30.     for(int i=0;i<=n;i++)
  31.     	dist[i]=INT_MAX;
  32.     dist[0]=0;
  33.  
  34.     priority_queue<pii,vector<pii>,greater<pii> >pq;
  35.  
  36.     pq.push(make_pair(0,0));
  37.     while(!pq.empty())
  38.     {
  39.         pii temp=pq.top();
  40.         pq.pop();
  41.  
  42.         if(vis[temp.second])
  43.         	continue;
  44.         vis[temp.second]=1;
  45.         for(auto u:v[temp.second])
  46.         {
  47.             if(!vis[u.first]&&dist[u.first]>temp.first+u.second)
  48.             {
  49.                 dist[u.first]=dist[temp.second]+u.second;
  50.                 pq.push(make_pair(dist[u.first],u.first));
  51.             }
  52.         }
  53.     }
  54.     cout<<dist[n]<<endl;
  55.     return 0;
  56. }
Success #stdin #stdout 0s 4536KB
comments (?)
stdin
copy 
5
1 2 3 4 100
stdout
copy 
10
https://ideone.com/CuIkLt
language:
C++14 (gcc 8.3)
created:
3 years 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!