Bạn và người bạn Pinky có kế hoạch thống trị thế giới. Nhưng trước hết, hai người phải vô hiệu hóa một vũ khí bí mật.

Vũ khí nằm trong một mê cung lối đi ngoằn ngoèo (một đồ thị) có một lối vào. Pinky sẽ ở đỉnh chứa vũ khí bí mật để vô hiệu hóa nó. Trong lúc đó, một đội an ninh ở lối vào được báo động và chạy qua đồ thị, cố tới chỗ Pinky kịp lúc để ngăn cậu ấy. Bạn sẽ làm chậm đội an ninh để Pinky có nhiều thời gian nhất có thể.

Đi qua một cạnh của đồ thị tốn một đơn vị thời gian. Ngoài ra, bạn có thể “cản trở” nhiều nhất \(K\) đỉnh. Đi qua một đỉnh bị cản tốn thêm một đơn vị thời gian. Bạn sẽ chọn một tập đỉnh bị cản sao cho làm đội an ninh chậm nhất có thể.

Đội an ninh bắt đầu ở lối vào và cố tới đỉnh vũ khí bí mật. Hỏi họ mất bao lâu để tới đó? Bạn phải quyết định tất cả các vật cản trước khi họ bắt đầu hành trình. Họ biết những đỉnh nào đã bị cản và sẽ chọn đường đi tối ưu dựa trên thông tin đó.

Cản trở chính đỉnh chứa vũ khí không có ích, vì sau khi đã bắt được Pinky thì việc đi qua đỉnh ấy không làm họ chậm thêm nữa. Ngược lại, cản trở lối vào hiển nhiên là một ý hay.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,M,K\), rồi \(M\) cạnh u v với \(u<v\), không trùng; các cạnh hai chiều.

Dữ liệu ra

In Case #x: y, thời gian bảo vệ tới đích.

Ràng buộc

• \(1\le T\le100\), \(2\le N\le100\), \(1\le M\le N(N-1)/2\), \(1\le K\le N\); luôn có đường 0 tới \(N-1\).

Phân nhóm

• Nhỏ: với \(K\) đã cho, không thể tăng quá 2 so với đường ngắn nhất không cản.
• Lớn: không thêm ràng buộc.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
3 2 1
0 1
1 2
3 2 2
0 1
1 2
3 2 3
0 1
1 2
4 4 2
0 1
0 2
1 3
2 3
7 11 3
0 1
0 2
0 3
1 4
1 5
2 4
2 5
3 4
3 5
4 6
5 6

Case #1: 3
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 5

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Taking Over The World.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.