HackerEarth Minimum cost problem solution

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.

`#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';    }}`