trang chủ / đề bài / icpcwf05_c

Bài toán các giám khảo đi xe

Đề bài

Mô tả

Một nhóm giám khảo cần tụ họp để chấm một cuộc thi được tổ chức tại một thành phố, và họ cần tìm cách thuê ô tô rẻ nhất để đưa mọi người đến nơi thi. Họ nhận thấy có thể rẻ hơn nếu vài giám khảo đi chung một xe thuê trên toàn bộ hoặc một phần chặng đường, nhờ đó giảm tổng chi phí. Nhiệm vụ của bạn là xác định các lộ trình mà các giám khảo nên đi để tổng chi phí thuê xe là nhỏ nhất.

Ta có các giả thiết sau:

  • Chi phí thuê một xe tỉ lệ với quãng đường xe chạy. Không tính thêm tiền khi xe chở nhiều người, tiền xăng, bảo hiểm hay tiền trả xe ở thành phố khác với thành phố thuê xe.
  • Mọi xe thuê đều tính cùng một giá cho mỗi dặm.
  • Một xe thuê chở được bao nhiêu hành khách cũng được.
  • Giữa hai thành phố có nhiều nhất một con đường nối trực tiếp. Mỗi con đường đi được hai chiều và có độ dài là một số nguyên dương.
  • Từ thành phố xuất phát của mỗi giám khảo luôn có ít nhất một lộ trình đến thành phố tổ chức cuộc thi.
  • Mọi giám khảo có lộ trình xuất phát từ hoặc đi qua cùng một thành phố thì đi cùng nhau từ thành phố đó đến nơi thi. (Một giám khảo có thể đến một thành phố bằng một xe và rời thành phố đó bằng một xe khác.)

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test gồm một bản đồ đường đi, thành phố đích nơi tổ chức cuộc thi và các thành phố nơi các giám khảo đang ở.

Mỗi bộ test là một dãy số nguyên, cách nhau bởi dấu cách và/hoặc dấu xuống dòng. Thứ tự và ý nghĩa của các số như sau:

  • NC: số thành phố có trên bản đồ, các thành phố được đánh số từ 1 đến NC.
  • DC: số hiệu của thành phố đích.
  • NR: số con đường trên bản đồ. Mỗi con đường nối một cặp thành phố khác nhau.
  • Với mỗi con đường trong NR con đường: ba số nguyên C1, C2 và DIST. C1 và C2 là hai thành phố được con đường nối, DIST là độ dài của con đường đó.
  • NJ: số giám khảo.
  • NJ số nguyên, mỗi số ứng với một giám khảo: số hiệu thành phố nơi giám khảo đó đang ở.

Sau bộ test cuối cùng là một dòng chứa số nguyên −1.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (1,2,…) và tổng quãng đường ngắn nhất mà các xe thuê phải chạy để đưa các giám khảo đến nơi thi, theo dạng Case k: distance = D. Sau đó in danh sách lộ trình của các giám khảo, mỗi lộ trình trên một dòng, theo đúng thứ tự các thành phố xuất phát trong dữ liệu vào. Mỗi lộ trình gồm các thành phố mà giám khảo tương ứng phải đi qua, theo thứ tự đi qua, bắt đầu bằng thành phố xuất phát của giám khảo và kết thúc bằng thành phố tổ chức cuộc thi. Các số trong lộ trình cách nhau bởi dấu -, và trước mỗi lộ trình in ba dấu cách. Nếu giám khảo đang ở sẵn thành phố đích thì lộ trình chỉ gồm một thành phố đó.

Nếu có nhiều bộ lộ trình cùng có tổng quãng đường nhỏ nhất, chọn bộ dùng ít thành phố nhất (tính mọi thành phố xuất hiện trong các lộ trình). Nếu có nhiều tập thành phố cùng số phần tử dùng được, chọn tập đứng đầu theo thứ tự từ điển khi liệt kê các thành phố theo số hiệu tăng dần (ví dụ (2,3,6) chứ không phải (2,5,10)). Nếu vẫn còn nhiều cách, in bộ lộ trình nào thỏa mãn các yêu cầu trên cũng được.

Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 1≤NC≤20, 1≤DC≤NC.
  • 0≤NR≤NC(NC−1)/2; 1≤C1,C2≤NC, C1≠C2, không có hai con đường nối cùng một cặp thành phố; 1≤DIST≤1000.
  • 1≤NJ≤10. Nhiều giám khảo có thể ở cùng một thành phố, kể cả thành phố đích.
  • Từ thành phố của mỗi giám khảo luôn đi được đến thành phố đích.
  • Mỗi file có không quá 20 bộ test.

Ví dụ

Input Output Giải thích
5
3
5
1 2 1
2 3 2
3 4 3
4 5 1
2 4 2
2
5 1
4
4
3
1 3 1
2 3 2
3 4 2
2
1 2

3 3 3
1 2 2
1 3 3
2 3 1
2 2 1

-1
Case 1: distance = 6
5-4-2-3
1-2-3
Case 2: distance = 5
1-3-4
2-3-4
Case 3: distance = 3
2-3
1-2-3
Bộ 1: hai giám khảo đi chung đoạn 2→3, tổng 1+2+2+1=6 (đi riêng 5→4→3 tốn 4 và 1→2→3 tốn 3, tổng 7). Bộ 3: giám khảo ở thành phố 1 đi qua thành phố 2 rồi đi chung với giám khảo thứ nhất, tổng 2+1=3. Mỗi dòng lộ trình bắt đầu bằng ba dấu cách.
3
3
3
1 2 1
2 3 1
1 3 2
1
1
4
4
4
1 3 1
3 4 1
1 2 1
2 4 1
1
1
4
1
3
1 2 5
2 3 1
3 4 1
4
4 1 4 2
1
1
0
2
1 1
-1
Case 1: distance = 2
1-3
Case 2: distance = 2
1-2-4
Case 3: distance = 7
4-3-2-1
1
4-3-2-1
2-1
Case 4: distance = 0
1
1
Bộ 1: 1→3 và 1→2→3 cùng dài 2, chọn cách dùng ít thành phố hơn. Bộ 2: tập (1,2,4) đứng trước (1,3,4). Bộ 3: giám khảo thứ hai đã ở thành phố đích 1. Bộ 4: chỉ có một thành phố, không có con đường 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