trang chủ / đề bài / icpcwf08_k

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ộ 1) tới góc dưới bên phải (giao lộ 16); giao lộ ở hàng r, cột c được đánh số 4(r−1)+c.

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 9 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à 108. Đường đi theo các con phố có thời gian 10 (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à 100.

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 R, C, r1, c1, r2, c2. R và C là kích thước thành phố, (r1,c1) là toạ độ điểm xuất phát và (r2,c2) là toạ độ nhà của Johnny. Điểm xuất phát khác nhà của Johnny.

Sau sáu số đó là C−1 số nguyên không âm là thời gian đi qua các con phố giữa các giao lộ (1,1) và (1,2), (1,2) và (1,3), (1,3) và (1,4), v.v. Tiếp theo là C số nguyên không âm là thời gian đi qua các con phố giữa các giao lộ (1,1) và (2,1), (1,2) và (2,2), v.v. Sau đó, lại có C−1 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 R hàng gồm C−1 số xen kẽ với R−1 hàng gồm C số).

Mỗi số nguyên là thời gian cần để đi qua con phố tương ứng (không quá 10000), 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 0, 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ố 0.

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ừ 1) và thời gian nhỏ nhất cần để đi từ giao lộ (r1,c1) tới giao lộ (r2,c2), 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

  • 1≤r1,r2≤R≤100, 1≤c1,c2≤C≤100, (r1,c1)≠(r2,c2).
  • Thời gian của mỗi con phố là số nguyên từ 0 đến 10000.
  • Tổng R·C của mọi bộ test trong một file không vượt quá 105 (đề 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 (1,1) với (2,1) và (1,2) với (2,2)), cả hai con phố ngang đều bằng 0 nên không tới được (2,2).
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: 2·5. Bộ 2: đi thẳng, chỉ con phố giữa đi hết tốc độ: 6+3+6. Bộ 3: đi thẳng tới (1,4), quay đầu về (1,3) rồi rẽ xuống (2,3): 2+100+2+2+2=108, rẻ hơn rẽ ngay tại (1,3) (2+200+2=204). Bộ 4: đi thẳng qua nhà (1,3) tới (1,4), quay đầu về nhà: 2+10000+2+2=10006. Bộ 5: không có con phố dọc nào.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0