1491B.md (3092B)
1 Source: https://codeforces.com/problemset/problem/1491/B 2 3 B. Minimal Cost 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 There is a graph of $n$ rows and $10^6 + 2$ columns, where rows are numbered from $1$ to $n$ and columns from $0$ to $10^6 + 1$: 22 23  24 25 Let's denote the node in the row $i$ and column $j$ by $(i, j)$. 26 27 Initially for each $i$ the $i$-th row has exactly one obstacle — at node $(i, a_i)$. You want to move some obstacles so that you can reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph (you can't pass through obstacles). Moving one obstacle to an adjacent by edge free node costs $u$ or $v$ coins, as below: 28 29 * If there is an obstacle in the node $(i, j)$, you can use $u$ coins to move it to $(i-1, j)$ or $(i+1, j)$, if such node exists and if there is no obstacle in that node currently. 30 * If there is an obstacle in the node $(i, j)$, you can use $v$ coins to move it to $(i, j-1)$ or $(i, j+1)$, if such node exists and if there is no obstacle in that node currently. 31 * Note that you can't move obstacles outside the grid. For example, you can't move an obstacle from $(1,1)$ to $(0,1)$. 32 33 Refer to the picture above for a better understanding. 34 35 Now you need to calculate the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles. 36 37 Input 38 39 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 40 41 The first line of each test case contains three integers $n$, $u$ and $v$ ($2 \le n \le 100$, $1 \le u, v \le 10^9$) — the number of rows in the graph and the numbers of coins needed to move vertically and horizontally respectively. 42 43 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — where $a_i$ represents that the obstacle in the $i$-th row is in node $(i, a_i)$. 44 45 It's guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^4$. 46 47 Output 48 49 For each test case, output a single integer — the minimal number of coins you need to spend to be able to reach node $(n, 10^6+1)$ from node $(1, 0)$ by moving through edges of this graph without passing through obstacles. 50 51 It can be shown that under the constraints of the problem there is always a way to make such a trip possible. 52 53 Example 54 55 Input 56 57 ``` 58 3 59 2 3 4 60 2 2 61 2 3 4 62 3 2 63 2 4 3 64 3 2 65 ``` 66 67 Output 68 69 ``` 70 7 71 3 72 3 73 ``` 74 75 Note 76 77 In the first sample, two obstacles are at $(1, 2)$ and $(2,2)$. You can move the obstacle on $(2, 2)$ to $(2, 3)$, then to $(1, 3)$. The total cost is $u+v = 7$ coins. 78 79  80 81 In the second sample, two obstacles are at $(1, 3)$ and $(2,2)$. You can move the obstacle on $(1, 3)$ to $(2, 3)$. The cost is $u = 3$ coins. 82 83 