Ladders

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
 
#define int long long
using namespace std;
 
void solve()
{
    int n;
    cin >> n;
 
    vector<int> nums(n, 0);
    vector<int> inds(n, 0);
    vector<vector<int>> adj(n, vector<int>());
 
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
        nums[i]--;
        inds[nums[i]] = i;
    }
    for (int i = 0; i < n; i++)
    {
        int val = nums[i]+1;
        adj[i].push_back(i+1);
        for (int j = 2*val; j <= n; j += val)
        {
            adj[i].push_back(inds[j-1]);
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(adj.size(), LLONG_MAX);
    vector<int> next(adj.size(), 0);
    vector<int> visited(adj.size(), false);
 
    pq.push({0, 0});
    dist[0] = 0;
 
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u])
            continue;
        visited[u] = true;
 
        // Iterate through all adjacent vertices of the current vertex
        for (auto &neighbor : adj[u]) {
            int v = neighbor;
            int weight = 1;
 
            // If a shorter path to v is found
            if (!visited[v] && dist[v] > dist[u] + weight) {
                // Update distance and push new distance to the priority queue
                dist[v] = dist[u] + weight;
                next[u] = v;
                pq.push({dist[v], v});
            }
        }
    }
 
/*
    int curr = 1;
    while (curr != n)
    {
        cout << curr << " ";
        curr = next[curr];
    }
    */
   cout << dist[n-1] << endl;
}
 
signed main()
{
    int t = 1;
 
    //cin >> t;
 
    for (int i = 0; i < t; i++)
        solve();
 
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED