← 返回题目列表

AtCoder · abc325_e

H. 我们的客户请稍等

中文机器翻译题面 查看原题

分数: 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