In this HackerEarth Minimum cost problem solution, You are standing at position 1. From position i, you can walk to i+1 or i-1 with cost 1. From position i, you can travel to without any cost to pi (p is a permutation of numbers 1...n). You have to reach position n. Determine the minimum possible cost.

HackerEarth Minimum cost problem solution


HackerEarth Minimum cost problem solution.

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 17;
int n, d[maxn], p[maxn];
bool mark[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n;
for(int i = 0; i < n; i++)
cin >> p[i], p[i]--;
fill(d + 1, d + n, n);
memset(mark, 0, sizeof mark);
queue<int> q({0});
while(q.size()){
int i = q.front();
q.pop();
if(mark[i])
continue;
mark[i] = 1;
vector<int> self({i});
while(p[self.back()] != i){
self.push_back(p[self.back()]);
d[self.back()] = d[i];
mark[self.back()] = 1;
}
auto add = [&](int j){
if(d[j] <= d[i] + 1)
return ;
d[j] = d[i] + 1;
q.push(j);
};
for(auto i : self){
if(i)
add(i - 1);
if(i < n - 1)
add(i + 1);
}
}
cout << d[n - 1] << '\n';
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 17;
int n, d[maxn], p[maxn];
bool mark[maxn];
int main(){
ios::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while(t--){
cin >> n;
for(int i = 0; i < n; i++)
cin >> p[i], p[i]--;
fill(d + 1, d + n, n);
memset(mark, 0, sizeof mark);
queue<int> q({0});
while(q.size()){
int i = q.front();
q.pop();
if(mark[i])
continue;
mark[i] = 1;
vector<int> self({i});
while(p[self.back()] != i){
self.push_back(p[self.back()]);
d[self.back()] = d[i];
mark[self.back()] = 1;
}
auto add = [&](int j){
if(d[j] <= d[i] + 1)
return ;
d[j] = d[i] + 1;
q.push(j);
};
for(auto i : self){
if(i)
add(i - 1);
if(i < n - 1)
add(i + 1);
}
}
cout << d[n - 1] << '\n';
}
}