trang chủ / đề bài / icpc24_reg_b

Tàu cao tốc

Đề bài

Mô tả

Năm 2207, đất nước PVH trở thành một trong những quốc gia nhộn nhịp nhất thế giới. Để đáp ứng nhu cầu đi lại giữa các thành phố đang tăng nhanh, đồng thời giảm khí thải từ máy bay, chính phủ dự định xây dựng một hệ thống tàu cao tốc.

Đất nước PVH có n thành phố, đánh số từ 1 đến n. Mỗi thành phố có đúng một nhà ga trung tâm, nơi các chuyến tàu khởi hành và đến. Hệ thống đường ray hiện tại cho phép tàu chạy thẳng giữa mọi cặp thành phố. Khoảng cách giữa nhà ga của hai thành phố i và j là di,j, với di,j=dj,i cho mọi cặp (i,j) và di,i=0 cho mọi i.

Chính phủ dự định vận hành một số tuyến tàu. Mỗi tuyến khởi hành từ một nhà ga, đi qua một số nhà ga khác và kết thúc ở một nhà ga nào đó. Trên một tuyến, tàu không được đi qua một nhà ga quá một lần và tuyến có không quá k nhà ga (tính cả ga đầu và ga cuối). Chi phí vận hành một tuyến là tổng khoảng cách giữa các cặp nhà ga liên tiếp.

Chính xác hơn, một tuyến là một dãy số nguyên x1,x2,…,xt thoả mãn:

  • 1≤x1,x2,…,xt≤n;
  • 2≤t≤k;
  • x1,x2,…,xt đôi một phân biệt.

Chi phí vận hành tuyến này là dx1,x2+dx2,x3+…+dxt−1,xt.

Có m cặp thành phố quan trọng, giữa chúng có hàng triệu người đi lại mỗi năm. Với mỗi cặp quan trọng (u,v), chính phủ muốn có ít nhất một tuyến đi qua cả u và v. Thứ tự không quan trọng: hai cặp (u,v) và (v,u) được coi là một.

Hãy giúp đất nước PVH thiết kế các tuyến tàu sao cho mọi cặp quan trọng đều được phục vụ và tổng chi phí vận hành các tuyến là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên: số bộ test. Mỗi bộ test có dạng:

  • Dòng đầu tiên chứa ba số nguyên n, k, m (2≤k≤n≤19, 1≤m≤15).
  • Trong n−1 dòng tiếp theo, dòng thứ i (1≤i≤n−1) chứa n−i số nguyên di,i+1,di,i+2,…,di,n (1≤di,j≤1312).
  • m dòng cuối, mỗi dòng chứa hai số nguyên u và v (1≤u<v≤n) mô tả một cặp thành phố quan trọng.

Dữ liệu đảm bảo:

  • tổng n trên tất cả các bộ test không vượt quá 95;
  • tổng m trên tất cả các bộ test không vượt quá 75.

Dữ liệu ra

Với mỗi bộ test:

  • Dòng đầu tiên chứa hai số nguyên b và c: chi phí vận hành nhỏ nhất và số tuyến tàu.
  • c dòng tiếp theo, mỗi dòng chứa một số nguyên t (2≤t≤k) và tiếp theo là t số nguyên x1,x2,…,xt (1≤xi≤n) mô tả một tuyến tàu.

Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ.

Ràng buộc

  • 2≤k≤n≤19, 1≤m≤15
  • 1≤di,j≤1312
  • Các cặp quan trọng có 1≤u<v≤n.
  • Tổng n trên tất cả các bộ test không vượt quá 95, tổng m không vượt quá 75.

Ví dụ

Input Output Giải thích
2
5 3 6
1 2 3 4
5 6 7
8 9
10
1 2
2 3
1 3
3 4
4 5
3 5
5 4 6
1 2 3 4
5 6 7
8 9
10
1 2
2 3
1 3
3 4
4 5
3 5
20 2
3 4 3 5
3 2 1 3
17 2
4 4 1 3 5
3 2 1 3
Bộ test thứ nhất: tuyến 4→3→5 (chi phí 8+9=17) phục vụ các cặp (3,4), (4,5), (3,5); tuyến 2→1→3 (chi phí 1+2=3) phục vụ (1,2), (2,3), (1,3). Bộ test thứ hai cho phép 4 nhà ga mỗi tuyến, tuyến 4→1→3→5 có chi phí 3+2+9=14.
1
4 2 2
1 100 100
100 100
1
1 3
2 4
200 2
2 1 3
2 2 4
Mỗi tuyến chỉ có tối đa 2 nhà ga nên mỗi cặp quan trọng cần một tuyến riêng 1→3 và 2→4, tổng chi phí 100+100=200.

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