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 căn hầm được đào sâu xuống mặt đất M tầng, mỗi tầng có N phòng. Các phòng được ngăn cách bằng các cửa rất khó phá. Các phòng có cửa xuống phòng ngay phía 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 khác nhau với độ dày khác nhau nên việc phá cửa cần thời gian khác nhau.

Bạn hãy tìm cách đi từ mặt đất xuống phòng của Bin Laden nhanh nhất không hắn thoát 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 các cánh 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 New Boy
Bai nay phai dung Dijkstra-Heap boi vi can xay dung 1 do thi m.n dinh ! 2222.10 = 22220 (dinh) la hop ly roi
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 Bứt Phá
mất hơn 2 tiếng đồng hồ mới tạo xong đồ thị, ke khiếp, không 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 cái đoạn xây đồ thị thôi. Nhưng mà cái đồ thị này cũng khá là lớn chứ ko khiêm tốn như cái kích thước đề bài
2014-06-19 19:05:37 Đức Anh
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 Nguyễn Ngọc Quang
Lần đầu cải thử dijkstra heap... xong áp dụng cho bài này luôn... 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 Ke Luon
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.