| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
VLPT12A - Cơm hộp |
Một cửa hàng bán cơm hộp bằng cách nhận các đặt hàng qua điện thoại, sau đó sẽ giao cơm đến tận nơi. Để tăng hiệu quả kinh doanh, năm nay cửa hàng này quyết định tìm một địa điểm mới để giảm thiểu chi phí vận chuyển.
Giả sử thành phố được mô tả qua một lưới hình chữ nhật. Các địa điểm cần đến và cả cửa hàng đều là các điểm giao nhau trên lưới. Dựa trên thống kê trong năm trước, người quản lý cửa hàng biết được số yêu cầu đặt cơm trong năm. Chi phí vận chuyển từ cửa hàng đến điểm có yêu cầu được tính theo khoảng cách Manhattan, tức là tổng số đơn vị theo chiều dọc và chiều ngang tối thiểu cần đi qua trên lưới. Tất nhiên ta chỉ tính chi phí vận chuyển đến chứ không tính đoạn đường quay về.
Hãy viết chương trình xác định chi phí vận chuyển tối thiểu trong năm qua nếu đặt cửa hàng sang vị trí tối ưu nhất.
Dữ liệu vào
Dòng 1 ghi số n là số bộ test (1<=n<=20).
Với mỗi bộ test, dòng đầu ghi hai số x,y là số cột và số dòng của lưới. 1<=x,y<=100.
y dòng tiếp theo, mỗi dòng ghi x giá trị cho biết số yêu cầu đặt cơm của mỗi điểm trong năm qua, các giá trị đều không quá 1000.
Kết quả
Với mỗi bộ test, ghi ra màn hình một số nguyên duy nhất là chi phí vận chuyển tối thiểu trong năm qua khi đặt cửa hàng ở vị trí tối ưu.
Example
Input:2
4 4
0 8 2 0
1 4 5 0
0 1 0 1
3 9 2 0
6 7
0 0 0 0 0 0
0 1 0 3 0 1
2 9 1 2 1 2
8 7 1 3 4 3
1 0 2 2 7 7
0 1 0 0 1 0
0 0 0 0 0 0
Output:55
162
| Được gửi lên bởi: | adm |
| Ngày: | 2012-09-29 |
| Thời gian chạy: | 10s |
| 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
|
2020-04-01 17:50:22
Ai giúp e với..em còn chưa hiểu cách output |
|
|
2018-03-26 17:34:53
x,y là số dòng, số cột đáp án để long long =)))) |
|
|
2017-08-21 09:59:43 Ðặng Minh Tiến
https://kienthuc24h.com/vlpt12a-spoj-ptit-com-hop/ |
|
|
2015-07-30 05:32:12 Nero
input :ohgod: |
|
|
2015-01-23 02:58:06 62
đệt! hóa ra có 2 cái abs :v Last edit: 2015-01-23 03:06:18 |
|
|
2014-10-31 08:21:59 Bác Ba Phì
Cái Test 2 ra 202 mới đúng. Đã thử và thành công. |
|
|
2014-08-07 14:48:13 Le Hoang
test 2 ra kq 202 day |
|
|
2014-06-30 20:54:39 Hat Dau Nho
test 2 kq 202 chu nhi :3 |
