/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
ある国には都市が N 個あります。
あなたは、都市 1 にある営業所から 0 個以上の都市を経由して都市 N にある訪問先へ移動しようとしています。
移動手段は社用車と電車の 2 種類があります。都市 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
以下のように移動することで合計 78 分で都市 1 から都市 4 に移動することができます。
- 都市 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
Score : 450 points
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