MDOSTAVA - Pizza Delivery

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mdostava


Công việc của Ivana là chuyển bánh pizza. Hàng ngày, anh ta nhận được 1 danh sách các địa điểm nhận bánh.

Thành phố được mô tả là bản đồ RxC ô, (1,1) cho đến RxC. Cho phép di chuyển từ 1 ô sang trái hoặc phải. Chỉ được phép đi lên/xuống ở cột 1 hoặc C.

Ivana xuất phát từ (1,1) và mang theo mọi bánh pizza cần chuyển. Tại mỗi ô, Ivana biết thời gian mà anh ta cần để đi qua ô đó. Tính thời gian nhỏ nhất để cung cấp tất cả các pizza. Biết rằng bánh pizza phải được cung cấp theo đúng thứ tự xuất hiện trong danh sách yêu cầu

Input

Dòng đầu là hai số R,c (1 ≤ R ≤ 2000, 1 ≤ C ≤ 200), R dòng tiếp theo, mỗi dòng C số nguyên >=0 và <=5000.

Dòng sau đó chứa D (1 ≤ D ≤ 200 000), số pizza cần chuyển. D dòng, mỗi dòng hai số A, B , (1 ≤ A ≤ R, 1 ≤ B ≤ C), vị trí nhận bánh.

Mỗi vị trí xuất hiện <=1 lần.

It calls pizza

Thời gian cung cấp pizza nhỏ nhất.

Sample

input
3 3
1 8 2
2 3 2
1 0 1
3
1 3
3 3
2 2
output
17

input
2 5
0 0 0 0 0
1 4 2 3 2
4
1 5
2 2
2 5
2 1
output
9

Ở ví dụ 1, cách đi nhanh nhất là : (1, 1), (2, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (2, 3), (3, 3), (2, 3) và (2, 2). và thời gian tương ứng là 1+2+1+0+1+2+2+2+1+2+3=17.


Được gửi lên bởi:psetter
Ngày:2009-03-08
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:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 6th 09

hide comments
2013-06-13 10:57:23 Cottontail Tee
Chật vật lên xuống cả buổi chiều vì quên xét TH 2 địa điểm kế tiếp nhau nằm cùng hàng T_T
2010-10-14 05:13:58 Siêu Nhân Trong Suốt
Time chặt quá :(( . AC bên spoj và phải submit tận 7 lần ở VOJ để mong 1 lần thần may mắn xuất hiện :D

Last edit: 2010-10-14 06:19:05
2009-10-11 13:17:28 TNO
Em thấy khó hiểu test 1 quá
tại sao fải qua ô (3,3) 2 lần khi có thể đi 1 lần qua (3,3) rồi đến ô (2,2)

Last edit: 2009-10-11 13:18:24
2009-05-19 02:43:12 dhkhtn
cai nay phai hoi BTC, nhung ma chac la duoc , xem cai vi du ay.
2009-05-19 02:42:08 Tue Le
Những ô đã đc cung cấp pizza rồi có đc đi vào lại ko ạ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.