分数: 450 点
问题陈述
有 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 分钟。
不可能从城市出发 1 前往城市 4 小于 78 分钟。
示例输入 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