Chuyến Bay Giá Rẻ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Có $N$ chuyến bay, mỗi chuyến bay đi qua một số thành phố theo thứ tự cố định và có chi phí cố định bất kể lên xuống ở điểm nào. Bạn muốn đi từ thành phố $A$ đến thành phố $B$ bằng đúng một chuyến bay: lên ở một điểm dừng có thành phố $A$ và xuống ở một điểm dừng sau đó có thành phố $B$ .

Tìm chi phí nhỏ nhất, hoặc $- 1$ nếu không có chuyến bay nào hợp lệ.

Dữ liệu vào

Dòng đầu chứa ba số nguyên $A$ , $B$ , $N$ .

$N$ dòng tiếp theo, mỗi dòng mô tả một chuyến bay: số nguyên $C$ (chi phí) và $K$ (số thành phố), tiếp theo là $K$ số nguyên là thứ tự các thành phố trên lộ trình.

Dữ liệu ra

Một số nguyên — chi phí nhỏ nhất, hoặc $- 1$ nếu không thể đến được.

Ràng buộc

$1 \leq N \leq 500$
$1 \leq C \leq 1000$
$2 \leq K \leq 500$
Số hiệu thành phố từ $1$ đến $10000$

Ví dụ

Input	Output	Giải thích
1 2 3 3 3 3 2 1 4 4 2 1 4 3 8 5 4 1 7 8 2	8	Chuyến 1: thành phố 2 xuất hiện trước 1 → không hợp lệ. Chuyến 2: tương tự. Chuyến 3: 1 ở vị trí đầu, 2 ở cuối → hợp lệ, chi phí 8.
10 4 10 580 5 5 3 10 4 7 282 10 2 6 4 8 9 3 5 10 7 1 273 8 10 6 5 9 7 3 8 4 379 5 7 6 10 4 9 953 3 2 10 1 203 5 9 8 1 6 10 831 4 5 10 3 8 561 8 7 10 8 2 5 3 6 4 732 3 8 2 1 428 6 1 7 3 4 2 5	273	Chuyến 3 (chi phí 273): lộ trình 10,6,5,9,7,3,8,4 chứa 10 trước 4 → hợp lệ.

Bình luận

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