Chuyến Bay Giá Rẻ II

Đ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ạn muốn đi từ thành phố $A$ đến thành phố $B$ bằng tối đa hai chuyến bay: mỗi chuyến bay bạn lên ở một điểm dừng và xuống ở một điểm dừng sau đó.

Tìm tổng chi phí nhỏ nhất, hoặc $- 1$ nếu không thể đến được.

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 — tổng 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	7	Dùng chuyến 2 từ 1→3 (giá 4), rồi chuyến 1 từ 3→2 (giá 3). Tổng 7.
3 4 3 3 5 1 2 3 4 5 2 3 3 5 4 1 2 1 5	2	Dùng một chuyến 2 từ 3→4 (giá 2).

Bình luận

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