Xe lu
Đề bài
Mô tả
Johnny lái một chiếc xe lu. Giống như mọi chiếc xe lu khác, xe của anh chạy chậm và cần khá nhiều thời gian để bắt đầu chuyển động, đổi hướng và phanh lại cho tới khi dừng hẳn. Johnny vừa xong việc trong ngày và đang lái xe lu về nhà gặp vợ. Nhiệm vụ của bạn là tìm đường đi nhanh nhất cho anh và chiếc xe lu.
Thành phố nơi Johnny sống có cấu trúc đều đặn (các con phố tạo thành một hệ vuông góc). Các con phố được bố trí theo một lưới chữ nhật gồm các giao lộ. Mỗi giao lộ được nối với các giao lộ láng giềng (nhiều nhất là bốn) bằng một con phố. Mỗi con phố dài đúng một khối nhà. Khi Johnny đã đi vào một con phố, anh luôn phải đi tới đầu kia của nó (tới giao lộ tiếp theo). Từ đó, anh có thể đi tiếp theo bất kỳ hướng nào trong bốn hướng tới một giao lộ khác, và cứ thế tiếp tục.
Bằng cách khảo sát tình trạng mặt đường, Johnny đã tính được thời gian cần để đi từ đầu này tới đầu kia của mỗi con phố trong thành phố. Thời gian này như nhau cho cả hai chiều. Tuy nhiên, các tính toán của Johnny chỉ đúng trong điều kiện lý tưởng: xe lu đang chuyển động sẵn khi đi vào con phố và không cần tăng tốc hay phanh. Mỗi khi xe lu đổi hướng tại giao lộ ngay trước hoặc ngay sau một con phố, thời gian lý tưởng của con phố đó phải được nhân đôi. Điều tương tự cũng áp dụng nếu xe lu bắt đầu chuyển động từ trạng thái đứng yên (chẳng hạn ở đầu chuyến đi của Johnny) hoặc phải dừng hẳn (chẳng hạn ở cuối chuyến đi) ở một đầu của con phố.
Hình dưới đây là một ví dụ. Các số là thời gian "lý tưởng" để đi qua các con phố tương ứng. Những con phố không được vẽ (thiếu số) là các con phố xe lu không đi được. Johnny muốn đi từ góc trên bên trái (giao lộ ) tới góc dưới bên phải (giao lộ ); giao lộ ở hàng , cột được đánh số .
graph weighted 1 2 10 2 3 10 3 4 10 1 5 9 4 8 10 5 9 9 8 12 10 9 10 9 10 14 9 12 16 10 14 15 9 15 16 9 pos 1 0 0 pos 2 100 0 pos 3 200 0 pos 4 300 0 pos 5 0 100 pos 6 100 100 pos 7 200 100 pos 8 300 100 pos 9 0 200 pos 10 100 200 pos 11 200 200 pos 12 300 200 pos 13 0 300 pos 14 100 300 pos 15 200 300 pos 16 300 300 label 1 Xuất phát label 16 Nhà path green 1 2 3 4 8 12 16
Thoạt nhìn, đường đi gồm các con phố có thời gian có vẻ nhanh hơn. Tuy nhiên, do các ràng buộc về tăng tốc và phanh, mọi con phố trên đường đó đều mất gấp đôi thời gian ước tính, nên tổng thời gian là . Đường đi theo các con phố có thời gian (tô màu xanh) nhanh hơn vì Johnny có thể đi hai con phố với tốc độ tối đa, cho tổng thời gian là .
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng sáu số nguyên dương , , , , , . và là kích thước thành phố, là toạ độ điểm xuất phát và là toạ độ nhà của Johnny. Điểm xuất phát khác nhà của Johnny.
Sau sáu số đó là số nguyên không âm là thời gian đi qua các con phố giữa các giao lộ và , và , và , v.v. Tiếp theo là số nguyên không âm là thời gian đi qua các con phố giữa các giao lộ và , và , v.v. Sau đó, lại có số nguyên không âm mô tả hàng phố ngang tiếp theo của thành phố. Dữ liệu cứ tiếp tục như vậy để mô tả mọi con phố trong thành phố (lần lượt hàng gồm số xen kẽ với hàng gồm số).
Mỗi số nguyên là thời gian cần để đi qua con phố tương ứng (không quá ), với điều kiện xe lu đi thẳng qua mà không khởi hành, dừng lại hay rẽ ở đầu nào của con phố. Nếu xảy ra một hoặc nhiều sự kiện trong số đó (với bất kỳ cách kết hợp nào), thời gian được nhân với hai. Bất kỳ số nào trong các số này cũng có thể bằng , khi đó con phố tương ứng hoàn toàn không đi được.
Sau bộ test cuối cùng là sáu số .
Các số được phân cách bởi ít nhất một ký tự khoảng trắng (dấu cách, tab hoặc xuống dòng), nhưng có thể có thêm khoảng trắng tuỳ ý (kể cả dòng trống) để dễ đọc.
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ) và thời gian nhỏ nhất cần để đi từ giao lộ tới giao lộ , theo định dạng Case i: T. Nếu không thể thực hiện chuyến đi (do có những con phố không đi được), in Case i: Impossible.
Ràng buộc
- , , .
- Thời gian của mỗi con phố là số nguyên từ đến .
- Tổng của mọi bộ test trong một file không vượt quá (đề gốc không giới hạn số bộ test).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 4 1 1 4 4 10 10 10 9 0 0 10 0 0 0 9 0 0 10 9 0 0 0 9 0 10 0 9 9 2 2 1 1 2 2 0 1 1 0 0 0 0 0 0 0 |
Case 1: 100 Case 2: Impossible |
Bộ 1 là thành phố trong hình. Bộ 2: chỉ có hai con phố dọc đi được (nối với và với ), cả hai con phố ngang đều bằng nên không tới được . |
| 1 2 1 1 1 2 5 1 4 1 1 1 4 3 3 3 2 4 1 1 2 3 1 100 1 0 0 1 0 0 0 0 2 4 1 1 1 3 1 10000 1 0 0 1 1 0 0 1 2 2 1 1 2 2 7 0 0 3 0 0 0 0 0 0 |
Case 1: 10 Case 2: 15 Case 3: 108 Case 4: 10006 Case 5: Impossible |
(Ví dụ tự thêm.) Bộ 1: con phố duy nhất vừa khởi hành vừa dừng: . Bộ 2: đi thẳng, chỉ con phố giữa đi hết tốc độ: . Bộ 3: đi thẳng tới , quay đầu về rồi rẽ xuống : , rẻ hơn rẽ ngay tại (). Bộ 4: đi thẳng qua nhà tới , quay đầu về nhà: . Bộ 5: không có con phố dọc nào. |
Bình luận