Minimum cost | Practice Problems

Minimum cost

★★★★★

43 votes

Algorithms, Breadth First Search, Easy, Graphs

Details

Submissions

Discussion

Editorial

Problem

You are standing at position . From position $i$ , you can walk to $i+1$ or $i-1$ with cost . From position , you can travel to without any cost to $p_i$ ( $p$ is a permutation of numbers $1 \ldots n$ ). You have to reach position $n$ . Determine the minimum possible cost.

Input format

First line: $T$ denotes the number of test cases ( $1 \le T \le 10$ )
For each test case:
- First line: $n$ ( $1 \le n \le 50\ 000$ )
- Second line: $n$ integers where the $i_{th}$ integer is $p_i$
  Note: It is guaranteed that $p$ is a permutation.

Output format
Print the minimum possible cost.

Sample Input

6
6
1 4 3 2 5 6
6
3 2 6 5 4 1
6
3 6 2 4 1 5
6
5 4 6 3 2 1
6
1 6 5 4 2 3
6
5 1 3 6 2 4

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Contributers:

Amirreza Poorakhavan

Amir Hossein