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
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 Nhọc
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???
2013-08-16 19:26:56 Con nt :xx
Bài này Dijkstra Heap à ?
2013-06-18 15:03:20 Tiếng em vang rừng ni...
tạo ồ thị lằng nhằng ghê :(

Last edit: 2013-07-19 07:38:19
2012-12-08 14:21:06 Việt Hùng
Theo mình làm thì
1. QH 60 iểm (thiếu trường hợp i lên)
2. Dijkstra 70 iểm
3. Dijkstra_Heap 100 iểm ^^
2012-10-26 16:43:16 ức
QH mà c c 40 =="
2011-11-12 16:49:53 trẻ tru sủa gu gu
tui.lam.O(n*m).ma.chi.dc.60%.ne!
2011-07-24 07:23:16 vodanh9x


Last edit: 2012-01-06 16:01:15
2011-06-14 14:33:23 Le Viet Thanh Long
O(m*n^2*log(m*n))

Last edit: 2011-07-11 11:50:35
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.