| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P146SUMC - ROUND 6C - Người vận chuyển |
Tí mới nhận được công việc mới là nhận chuyển phát nhanh. Đất nước của cậu có n thành phố. Cậu đang ở thành phố 1 và cần đến thành phố n.
Số lít xăng tiêu tốn đi lại giữa 2 thành phố là khoảng cách manhattan giữa 2 thành phố đó nhân với hằng số d, khi đến thành phố i, cậu được tiếp thêm a[i] lít xăng miễn phi tại chi nhánh của cậu, còn không thì cậu tự bỏ chi phí ra mua xăng. Các chi nhánh chỉ bơm xăng đúng 1 lần, vậy nên Tí đã bơm xăng 1 trạm rồi tại một thời điểm sau đó quay lại bơm xăng tiếp thì sẽ bị từ chối.
Xăng giá thì cao nên Tí muốn chọn một con đường để số xăng phải chuẩn bị cho chuyến đi là ít nhất. Các bạn tính giúp Tí nhé.
Input
Dòng đầu tiên gồm 2 số nguyên n và d (3 <=n <= 100, 10^3 <=d <= 10^5) – số thành phố và hằng số nhân chi phí.
Dòng tiếp theo gồm n – 2 số nguyên a[2], .., a[n-1] là số lít xăng miễn phí của chi nhánh thành phố i (1 <= a[i] <= 10^3).
n dòng tiếp, dòng thứ i là tọa độ của thành phố i gồm 2 số x[i], y[i] (-100 <= x[i], y[i] <=100).
Input đảm bảo không có 2 thành phố có cùng một tọa độ.
Output
Lượng xăng ít nhất mà Tí cần chuẩn bị cho chuyến đi.
Example
Test 1:
Input:
3 1000
1000
0 0
0 1
0 3
Output:
2000
Test 2:
Input:
3 1000
1000
1 0
1 1
1 2
Output:
1000
| Được gửi lên bởi: | adm |
| Ngày: | 2014-07-31 |
| Thời gian chạy: | 1s |
| 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
|
2016-04-17 19:17:32 Username
https://vi.wikipedia.org/wiki/Manhattan |
|
|
2015-04-11 10:49:05 Thiên Thiên
khoảng cách manhattan là gì vậy ? |
