Lộ Trình Khác Biệt II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bạn chơi một trò chơi trong $k$ ngày. Mỗi ngày, bạn bắt đầu tại phòng $1$ và cần đến phòng $n$ , di chuyển qua các máy dịch chuyển. Mỗi máy dịch chuyển chỉ có thể được sử dụng tối đa một lần trong toàn bộ $k$ ngày. Sử dụng một máy dịch chuyển tốn một đồng xu.

Tìm số đồng xu tối thiểu để hoàn thành đủ $k$ ngày, đồng thời in ra lộ trình của mỗi ngày.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $n$ , $m$ , $k$ — số phòng, số máy dịch chuyển, và số ngày cần hoàn thành.

$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ — mô tả máy dịch chuyển từ phòng $a$ đến phòng $b$ .

Dữ liệu ra

Nếu không thể hoàn thành $k$ ngày, in $- 1$ .

Ngược lại, dòng đầu tiên in số đồng xu tối thiểu. Tiếp theo, với mỗi ngày, in số phòng trên lộ trình (bao gồm phòng $1$ và phòng $n$ ) trên một dòng, và in các phòng trên dòng tiếp theo.

Ràng buộc

$2 \leq n \leq 500$
$1 \leq m \leq 1000$
$1 \leq k \leq n - 1$
Không có máy dịch chuyển trùng lặp giữa cùng hai phòng

Ví dụ

Input	Output	Giải thích
8 10 2 1 2 1 3 2 5 2 4 3 5 3 6 4 8 5 8 6 7 7 8	6 4 1 2 4 8 4 1 3 5 8	Ngày 1: đi qua 3 máy dịch chuyển (1→2→4→8). Ngày 2: đi qua 3 máy dịch chuyển (1→3→5→8). Tổng: 6 đồng xu.

Bình luận

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