103254: [Atcoder]ABC325 E - Our clients, please wait a moment

Problem Statement

There are $N$ cities in a certain country.
You will travel from your office in city $1$ to a destination in city $N$, via zero or more cities.
Two types of transportation are available: company car and train. The time required to travel from city $i$ to city $j$ is as follows:

• $D_{i,j} \times A$ minutes by company car, and
• $D_{i,j} \times B + C$ minutes by train.

You can switch from company car to train, but not vice versa.
You can do so without spending time, but only in a city.

What is the minimum time in minutes to travel from city $1$ to city $N$?

Constraints

• $2 \leq N \leq 1000$
• $1 \leq A, B, C \leq 10^6$
• $D_{i,j} \leq 10^6$
• $D_{i,i} = 0$
• $D_{i,j} = D_{j,i} > 0$ $(i \neq j)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $A$ $B$ $C$
$D_{1,1}$ $D_{1,2}$ $\ldots$ $D_{1,N}$
$D_{2,1}$ $D_{2,2}$ $\ldots$ $D_{2,N}$
$\vdots$
$D_{N,1}$ $D_{N,2}$ $\ldots$ $D_{N,N}$

Output

Print the answer as an integer.

Sample Input 1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

Sample Output 1

78

You can travel from city $1$ to city $4$ in a total of $78$ minutes by moving as follows.

• Travel by company car from city $1$ to city $3$. This takes $2 \times 8 = 16$ minutes.
• Travel by company car from city $3$ to city $2$. This takes $3 \times 8 = 24$ minutes.
• Travel by train from city $2$ to city $4$. This takes $5 \times 5 + 13 = 38$ minutes.

It is impossible to travel from city $1$ to city $4$ in less than $78$ minutes.

Sample Input 2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

Sample Output 2

1

Sample Input 3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

Sample Output 3

168604826785

问题描述

某个国家有$N$个城市。
你将从城市$1$的办公室出发，通过零个或多个城市，到达城市$N$的目的地。
有两种交通工具可供选择：公司车和火车。从城市$i$到城市$j$所需的时间如下：

• 公司车需要$D_{i,j} \times A$分钟，
• 火车需要$D_{i,j} \times B + C$分钟。

你可以从公司车切换到火车，但不能反过来。
你可以在城市中不花时间进行切换。

从城市$1$到城市$N$的最短时间是多少分钟？

约束条件

• $2 \leq N \leq 1000$
• $1 \leq A, B, C \leq 10^6$
• $D_{i,j} \leq 10^6$
• $D_{i,i} = 0$
• $D_{i,j} = D_{j,i} > 0$ $(i \neq j)$
• 所有输入值都是整数。

输入

输入从标准输入按以下格式给出：

$N$ $A$ $B$ $C$
$D_{1,1}$ $D_{1,2}$ $\ldots$ $D_{1,N}$
$D_{2,1}$ $D_{2,2}$ $\ldots$ $D_{2,N}$
$\vdots$
$D_{N,1}$ $D_{N,2}$ $\ldots$ $D_{N,N}$

输出

将答案作为整数打印。

样例输入1

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

样例输出1

78

你可以按照以下方式从城市$1$到城市$4$旅行，总共需要$78$分钟。

• 乘坐公司车从城市$1$到城市$3$。这需要$2 \times 8 = 16$分钟。
• 乘坐公司车从城市$3$到城市$2$。这需要$3 \times 8 = 24$分钟。
• 乘坐火车从城市$2$到城市$4$。这需要$5 \times 5 + 13 = 38$分钟。

无法在不到$78$分钟的时间内从城市$1$到城市$4$旅行。

样例输入2

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

样例输出2

1

样例输入3

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

样例输出3

168604826785