Educational Backtracking: Đi dạo

Xem dạng PDF

Gửi bài giải


Điểm: 0,60 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

[placeholder] rất lười vận động. Cậu suốt ngày ngồi ở nhà chơi điện tử. Một ngày, mẹ của [placeholder] rút dây máy tính, và bắt cậu ra ngoài đi dạo 1 vòng.

Nhà của [placeholder] nằm ở đỉnh ~1~ trong một đồ thị đầy đủ có hướng gồm ~n~ đỉnh. Các cạnh của đồ thị có trọng số. [placeholder] muốn tìm đi thăm ~k-1~ người bạn. Vì rất lười nên [placeholder] muốn chuyến đi dạo ngắn nhất có thể.

Bạn hãy giúp [placeholder] tìm một chu trình đơn giản có độ dài ~k~ có tổng trọng số các cạnh là nhỏ nhất.

Input

Dòng đầu tiên chứa 2 số ~n~, ~k~, số đỉnh của đồ thị và độ dài chu trình cần tìm (~n \le 50~, ~k \le min(n, 8), k~ chẵn).

~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số ~a_{i,j}~, độ dài cạnh từ đỉnh ~i~ đến đỉnh ~j~ (~1 \le a_{i,j} \le 100000, a_{i,i} = 0~)

Output

Dòng đầu chứa số ~s~ - độ dài của chu trình ngắn nhất. Dòng tiếp theo chứa ~k~ số - các đỉnh trên chu trình. Đỉnh đầu tiên của chu trình phải là đỉnh ~1~.

Sample Input 1

5 4
0 2 5 4 2 
9 0 5 3 7 
1 6 0 4 3 
9 7 8 0 5 
1 5 7 3 0 

Sample Output 1

11
1 2 3 5 

Bình luận

Hãy đọc nội quy trước khi bình luận.


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