Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT137K - BÀI K - TÌM ĐƯỜNG DÀI NHẤT

Trong một thị trấn nhỏ, các ngôi nhà đều có đường nối ra điểm giao sau đó từ điểm giao đi đến các ngôi nhà khác. Ví dụ sơ đồ các ngôi nhà (được đánh số) và các điểm giao (chấm tròn đen) có thể như sau:

 

Ở mỗi đoạn đường có giá trị trọng số là độ dài (tính theo mét) giữa mỗi nhà đến các điểm giao. Một người có ý định đi lang thang trong thị trấn từ ngôi nhà này đến một ngôi nhà khác, càng lâu càng tốt. Giả sử không có hai ngôi nhà nào nối trực tiếp đến nhau, và biết khoảng thời gian người đó đi được 1 mét đường và thời gian cần thiết để người đó đi qua một điểm giao cắt, hãy xác định khoảng thời gian dài nhất có thể cần thiết để đi từ nhà này đến nhà khác.

Ví dụ trong sơ đồ hình trên, cặp xa nhất sẽ là d3,9 = 9+1+7+6 = 23.

Biết người đó đi 1 mét mất 1 giây và đi qua một điểm giao mất 5 giây thì tổng thời gian dài nhất sẽ là: 1 × 23 + 3 × 5 = 38 giây.

Input

Có nhiều bộ test. Mỗi bộ test gồm:

  • Một dòng ghi ba số n, r, t với  n là số ngôi nhà (1<=n<=50), r là thời gian cần để đi một mét đường (1<=r<=10), t là thời gian để đi qua một điểm giao cắt (1<=t<=100).
  • n dòng tiếp theo, mỗi dòng có n giá trị dij ghi khoảng cách từ mỗi cặp hai ngôi nhà (1<=di,j<=1000). Ma trận khoảng cách được đảm bảo đối xứng (dij = dji).
  • Đầu vào kết thúc với một dòng ghi duy nhất một số 0.    

Output

Với mỗi bộ test, in ra màn hình trên một dòng khoảng thời gian dài nhất có thể.

Example

Input:

9 1 5

0 8 22 16 16 13 24 14 11

8 0 20 14 14 11 22 12 9

22 20 0 12 12 11 22 12 23

16 14 12 0 4 5 16 6 17

16 14 12 4 0 5 16 6 17

13 11 11 5 5 0 13 3 14

24 22 22 16 16 13 0 14 25

14 12 12 6 6 3 14 0 15

11 9 23 17 17 14 25 15 0

0
Output:
38
 

Được gửi lên bởi:adm
Ngày:2013-03-24
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-01-30 16:03:10 an IM3 Ex-Member of Bit
bài này đề bài dịch ko chuẩn lắm. Trong đồ thị có thể có điểm giao không nối trực tiếp với địa điểm nào. Tóm lại chỉ cần quan tâm 2 dữ kiện: 1) đồ thị đã cho là cây và 2) các địa điểm là lá.

Last edit: 2014-01-30 17:13:57
2014-01-30 09:35:17 Thích code nhưng dốt
Chú ý:
Không có ngôi nhà nào trùng với các điểm giao. Có thể coi đồ thị như một cây khung với các nút là các ngôi nhà và các điểm giao, mỗi điểm giao có bậc >= 3. Các cạnh đều có trọng số dương.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.