Giải bài trực tuyến

Từ tập các bài có trên SPOJ (oi)

2969. Bin Laden

Mã bài: BINLADEN

Bin Laden

Trùm khủng bố Bin Laden trốn trong 1 cn hầm ược ào su xuống mặt ất M tầng, mỗi tầng c N phòng. Cc phòng ược ngn cch bằng cc cửa rất kh ph. Cc phòng c cửa xuống phòng ngay pha dưới và 2 phòng ở 2 bên. Từ trên mặt ất c N cửa xuống N phòng tầng -1. Bin Laden ở tầng dưới cùng (tầng -M) phòng thứ N (phòng ở bên phải nhất). Mỗi cửa ược làm bằng một kim loại khc nhau với ộ dày khc nhau nên việc ph cửa cần thời gian khc nhau.

Bạn hãy tìm cch i từ mặt ất xuống phòng của Bin Laden nhanh nhất khng hắn thot mất.

Dữ liệu

  • Dòng 1 ghi M và N
  • Dòng 2 ến 2M + 1, dòng chẵn ghi N số, dòng lẻ ghi N - 1 số là chi ph ể ph cửa.

Kết quả

Ghi ra 1 số là thời gian nhỏ nhất ể ến ược phòng của Bin Laden

V dụ

Dữ liệu
4 2
99 10
1
10 99
1
99 10
1
10 99
1

Kết quả
44

+--99--+--10--+
|      |      |
|      1      |
|      |      |
+--10--+--99--+
|      |      |
|      1      |
|      |      |
+--99--+--10--+
|      |      |
|      1      |
|      |      |
+--10--+--99--+
|      |      |
|      1      |
|      |      |
+------+------+
i theo ường zigzac

Giới hạn

  • 1 <= M <= 2222
  • 1 <= N <= 10
  • Chi ph của cc cnh cửa thuộc [0, 1000].

Được gửi lên bởi:VOJ Team
Ngày:2008-09-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL JS NODEJS PERL 6
Nguồn bài:VNOI Marathon '08 - Round 12/DivB
Problem Setter: Lê n Khuê

hide comments
2014-08-08 08:58:57 ■■[ND] Bee Sociu■■
Ngon =)))))))) p/s : Test yeu :D hehe

Last edit: 2014-09-22 20:47:36
2014-08-05 17:50:22 Phantom
giới hạn to phết :v
2014-07-18 20:39:36 Phantom
anh dậu rất xung
2014-07-18 19:24:11 Mỹ Duyên (Genius Of The Effort)
mất hơn 2 tiếng ồng hồ mới tạo xong ồ thị, ke khiếp, khng kh nhưng làm lộn nên phải cài lại
2014-07-03 06:04:51 Hoàng Steven
Bài này chỉ mệt ci oạn xy ồ thị thi. Nhưng mà ci ồ thị này cũng kh là lớn chứ ko khiêm tốn như ci kch thước ề bài
2014-06-19 19:05:37 MNF FC&DI IMBB
Bài này dùng SPFA cũng AC (0.13s). Code ỡ nhọc hơn Dijkstra Heap :D
2014-05-14 10:40:34
Lần ầu cải thử dijkstra heap... xong p dụng cho bài này lun... 1 sub và AC ^^
2013-09-06 05:09:10 Phạm Thanh Hùng
Dij bình thường ược c mỗi 50 :(
2013-08-23 15:05:38 Khàn
nhìn qua nghĩ ngay QHD nhưng chắc ko full =='
2013-08-23 07:48:04 Sơn Sì
c bài OBAMA ko???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.