trang chủ / đề bài / icpcwf12_c

Tuyến xe buýt tham quan

Đề bài

Mô tả

Hãy tưởng tượng bạn là khách du lịch ở Warszawa và đã đặt một chuyến xe buýt tham quan tới một điểm du lịch tuyệt vời ở ngoại ô. Xe buýt trước hết chạy vòng quanh thành phố một lúc (khá lâu, vì Warszawa là một thành phố lớn) để đón khách ở các khách sạn của họ. Sau đó xe đi tới điểm du lịch, và vài giờ sau quay lại thành phố, lại đi tới từng khách sạn, lần này để trả khách.

Vì lý do nào đó, lần nào bạn đi, khách sạn của bạn cũng luôn là nơi được ghé đầu tiên khi đón khách và là nơi được ghé cuối cùng khi trả khách, nghĩa là bạn phải chịu đựng hai chuyến tham quan chẳng mấy thú vị qua tất cả các khách sạn trong vùng. Rõ ràng đó không phải điều bạn muốn (trừ khi bạn thực sự mê khách sạn), nên hãy sửa chuyện này. Ta sẽ viết một phần mềm giúp công ty du lịch sắp xếp các tuyến xe công bằng hơn, dù đôi khi tổng quãng đường của mọi người sẽ dài hơn, nhưng công bằng là trên hết, đúng không?

Trong bài này có một địa điểm xuất phát (trụ sở công ty du lịch), h khách sạn cần ghé để đón và trả khách, và một địa điểm đích (điểm du lịch). Ta cần tìm một tuyến đường đi từ trụ sở, qua tất cả các khách sạn, tới điểm du lịch, rồi quay lại qua tất cả các khách sạn một lần nữa (có thể theo thứ tự khác), và cuối cùng về trụ sở. Để bảo đảm không du khách nào (đặc biệt là bạn) phải chịu đựng hai vòng đầy đủ qua các khách sạn, ta yêu cầu: mọi khách sạn được ghé trong số ⌊h/2⌋ khách sạn đầu tiên trên đường tới điểm du lịch cũng phải được ghé trong số ⌊h/2⌋ khách sạn đầu tiên trên đường về. Thỏa mãn các ràng buộc đó, ta muốn toàn bộ chuyến đi càng ngắn càng tốt. Lưu ý rằng các ràng buộc này có thể buộc xe phải chạy ngang qua một khách sạn mà không dừng lại (không được tính là ghé) rồi mới ghé nó sau, như trong ví dụ đầu tiên.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Dòng đầu tiên của mỗi bộ test gồm hai số nguyên n và m (3≤n≤20, 2≤m), trong đó n là số địa điểm (các khách sạn, trụ sở, điểm du lịch) và m là số cặp địa điểm mà xe buýt có thể đi trực tiếp giữa chúng. n địa điểm được đánh số từ 0 tới n−1: 0 là trụ sở, 1 tới n−2 là các khách sạn (nên h=n−2), và n−1 là điểm du lịch. Giữa hai địa điểm bất kỳ có nhiều nhất một đường đi trực tiếp, và từ mọi địa điểm có thể đi tới mọi địa điểm khác (nhưng không nhất thiết đi trực tiếp).

Tiếp theo là m dòng, mỗi dòng gồm ba số nguyên u, v và t (0≤u,v≤n−1, u≠v, 1≤t≤3600), cho biết xe buýt có thể đi trực tiếp giữa hai địa điểm u và v (theo cả hai chiều) trong t giây.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test và thời gian (tính bằng giây) của chuyến đi ngắn nhất có thể, theo định dạng trong ví dụ.

Ràng buộc

  • 3≤n≤20, m≥2.
  • 0≤u,v≤n−1, u≠v, 1≤t≤3600.
  • Giữa hai địa điểm có nhiều nhất một đường đi trực tiếp; đồ thị liên thông.

Ví dụ

Input Output Giải thích
5 4
0 1 10
1 2 20
2 3 30
3 4 40
4 6
0 1 1
0 2 1
0 3 1
1 2 1
1 3 1
2 3 1
Case 1: 300
Case 2: 6
Bộ 1: các địa điểm nằm trên một đường thẳng 0−1−2−3−4, có h=3 khách sạn nên ⌊h/2⌋=1. Lượt đi 0→1→2→3→4 (100 giây) ghé khách sạn 1 đầu tiên, nên lượt về cũng phải ghé khách sạn 1 đầu tiên: từ 4 chạy ngang qua 3, 2 mà không dừng tới 1 (90 giây), rồi ghé 2, 3 (50 giây) và về 0 (60 giây). Tổng 300. Bộ 2: mọi cặp địa điểm đều nối trực tiếp với thời gian 1; tuyến 0→1→2→3→1→2→0 dài 6.
4 4
2 1 5
2 3 5
0 1 5
0 3 1
Case 1: 32 Các đường đi tạo thành chu trình 0−1−2−3−0. Lượt đi: 0→3 (chạy ngang qua điểm du lịch) →2, ghé 2, rồi tới 1, rồi 1→0→3, tổng 1+5+5+5+1=17. Lượt về ghé 2 đầu tiên: 3→2→1→0, tổng 15. Cả chuyến dài 32.

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