trang chủ / đề bài / icpcwf06_a

Đi máy bay giá rẻ

Đề bài

Mô tả

Giá vé máy bay thật điên rồ! Giá một vé được quyết định bởi rất nhiều yếu tố và thường không liên quan trực tiếp đến quãng đường bay. Nhiều hành khách tìm cách sáng tạo, đôi khi chỉ dùng một phần của vé, dừng ở nhiều thành phố khác nhau để đi được rẻ hơn. Tuy nhiên, các hãng hàng không biết rõ chuyện này và thường yêu cầu hành trình ghi trên một vé phải được đi theo đúng thứ tự và không được xen ngang bởi chuyến đi khác. Ví dụ, nếu bạn có một vé đi từ Thành phố 1 đến Thành phố 2 rồi đến Thành phố 3, bạn không được chỉ dùng phần vé từ Thành phố 2 đến Thành phố 3. Bạn luôn phải bắt đầu từ thành phố đầu tiên ghi trên vé. Ngoài ra, bạn cũng không được đi từ Thành phố 1 đến Thành phố 2, bay đi nơi khác rồi quay lại, sau đó mới tiếp tục hành trình từ Thành phố 2 đến Thành phố 3.

Xét một ví dụ. Giả sử bạn được phép mua ba loại vé:

Vé Lộ trình Giá
Vé số 1 Thành phố 1 đến Thành phố 3 đến Thành phố 4 225
Vé số 2 Thành phố 1 đến Thành phố 2 200
Vé số 3 Thành phố 2 đến Thành phố 3 50

Giả sử bạn muốn đi từ Thành phố 1 đến Thành phố 3. Chỉ dùng các loại vé trên, có hai cách để đến nơi:

  • Mua Vé số 1 với giá 225 và chỉ dùng chặng đầu tiên của vé.
  • Mua Vé số 2 với giá 200 và Vé số 3 với giá 50.

Cách thứ nhất rẻ hơn.

Cho một tập các loại vé được chào bán và một hoặc nhiều lịch trình chuyến đi, hãy xác định cách mua vé để tổng chi phí là nhỏ nhất. Mọi chuyến đi đều thực hiện được.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test, mỗi bộ mô tả một tập các loại vé chào bán và một tập các lịch trình chuyến đi.

Mỗi bộ test bắt đầu bằng một dòng chứa NT, số loại vé chào bán, tiếp theo là NT dòng mô tả các loại vé, mỗi dòng một loại. Mỗi mô tả gồm một số nguyên dương là giá vé, số thành phố trên lộ trình của vé, rồi đến chính các thành phố đó (theo thứ tự đi). Trong một bộ test, mỗi thành phố có một số hiệu nguyên tuỳ ý nhưng duy nhất. Lưu ý rằng có thể mua nhiều vé của cùng một loại.

Dòng tiếp theo chứa NI, số chuyến đi cần tính chi phí nhỏ nhất. Tiếp theo là NI dòng, mỗi dòng là lịch trình của một chuyến đi: số thành phố trong lịch trình (tính cả thành phố xuất phát), rồi đến chính các thành phố đó theo thứ tự phải ghé thăm.

Các loại vé và các chuyến đi trong mỗi bộ test được đánh số liên tiếp, bắt đầu từ 1.

Sau bộ test cuối cùng là một dòng chứa số 0.

Dữ liệu ra

Với mỗi chuyến đi, in hai dòng gồm số thứ tự bộ test, số thứ tự chuyến đi, chi phí nhỏ nhất của chuyến đi, và số hiệu các loại vé được dùng theo đúng thứ tự sử dụng, theo định dạng như ví dụ (dòng thứ hai bắt đầu bằng hai dấu cách). Kết quả luôn là duy nhất.

Ràng buộc

  • 1≤NT≤20, 1≤NI≤20.
  • Mỗi loại vé và mỗi lịch trình có từ 2 đến 10 thành phố; hai thành phố kề nhau trên một lộ trình hay một lịch trình luôn khác nhau.
  • Giá mỗi vé là số nguyên từ 1 đến 10000.
  • Số hiệu thành phố là số nguyên từ 1 đến 109.
  • Mỗi file có không quá 100 bộ test.
  • Mọi chuyến đi đều thực hiện được, và dãy vé tối ưu của mỗi chuyến đi là duy nhất.

Ví dụ

Input Output Giải thích
3
225 3 1 3 4
200 2 1 2
50 2 2 3
1
2 1 3
3
100 2 2 4
100 3 1 4 3
200 3 1 2 3
2
3 1 4 3
3 1 2 4
0
Case 1, Trip 1: Cost = 225
Tickets used: 1
Case 2, Trip 1: Cost = 100
Tickets used: 2
Case 2, Trip 2: Cost = 300
Tickets used: 3 1
Bộ 1 là ví dụ trong đề. Bộ 2, chuyến 1: vé 2 đi qua đúng 1,4,3. Chuyến 2: dùng vé 3 từ 1 đến 2 (bỏ phần còn lại), rồi vé 1 từ 2 đến 4. Vé 2 không dùng được vì nó đến 4 mà chưa qua 2.
4
30 3 5 9 7
40 2 9 8
100 2 5 8
60 4 8 5 8 7
2
2 5 8
3 8 5 7
0
Case 1, Trip 1: Cost = 70
Tickets used: 1 2
Case 1, Trip 2: Cost = 60
Tickets used: 4
Ví dụ tự thêm. Chuyến 1: dùng vé 1 đến thành phố 9 (không có trong lịch trình), đổi sang vé 2 đến 8, tổng 70<100. Chuyến 2: vé 4 đi 8,5,8,7 nên ghé đủ 8,5,7 theo thứ tự với giá 60.

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