#PU1093. USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths
USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths
USACO 2021 January Contest, Platinum — Problem 2. Minimum Cost Paths
题目描述
Farmer John's pasture can be regarded as an (, ) 2D grid of square "cells" (picture a huge chessboard). The cell at the -th row from the top and -th column from the right is denoted by for each . Furthermore, for each , the -th column is associated with the cost (). Bessie starts at the cell . If she is currently located at the cell , then she may perform one of the following actions: If , Bessie may move to the next column (increasing by one) for a cost of . If , Bessie may move to the next row (increasing by one) for a cost of . Given () independent queries each of the form (), compute the minimum possible total cost for Bessie to move from to .
输入格式
The first line contains and . The second line contains space-separated integers . The third line contains . The last lines each contain two space-separated integers and .
输出格式
lines, containing the answers for each query.
数据范围
Test cases 1-3 satisfy . Test cases 4-8 satisfy . Test cases 9-15 satisfy . Test cases 16-20 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
5 4
1 100 100 20
20
1 1
2 1
3 1
4 1
5 1
1 2
2 2
3 2
4 2
5 2
1 3
2 3
3 3
4 3
5 3
1 4
2 4
3 4
4 4
5 4
0
1
2
3
4
1
5
11
19
29
2
9
20
35
54
3
13
29
49
69
The output in grid format:
1 2 3 4
*--*--*--*--*
1 | 0| 1| 2| 3|
*--*--*--*--*
2 | 1| 5| 9|13|
*--*--*--*--*
3 | 2|11|20|29|
*--*--*--*--*
4 | 3|19|35|49|
*--*--*--*--*
5 | 4|29|54|69|
*--*--*--*--*
提示
use of 64-bit integer data types (e.g., a "long long" in C/C++).