Chuyến Bay Giá Rẻ (Silver)

Đ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 bất kỳ số lần sử dụng các chuyến bay (có thể dùng lại). Khi dùng một chuyến bay, bạn lên ở một điểm dừng và xuống ở một điểm dừng sau đó; chi phí là giá cả chuyến bay đó, và số "chặng" là số vị trí bạn đi qua trừ đi 1 (kể cả điểm giữa).

Tìm tổng chi phí nhỏ nhất, và trong tất cả cách đạt chi phí đó, tìm cách có số chặng nhỏ nhất. In -1 -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

Hai số nguyên: tổng chi phí nhỏ nhất và số chặng nhỏ nhất; hoặc -1 -1.

Ràng buộc

$1 \leq N \leq 1000$
$1 \leq C \leq 10^{9}$
$2 \leq K \leq 1000$
Số hiệu thành phố từ $1$ đến $1000$

Ví dụ

Input	Output	Giải thích
3 4 3 3 5 1 2 3 4 5 2 3 3 5 4 1 2 1 5	2 2	Dùng chuyến 2 từ 3→5→4: chi phí 2, qua 2 chặng (3→5 và 5→4).
1 2 3 3 3 3 2 1 4 4 2 1 4 3 5 5 2 5 7 8 3	7 3	Dùng chuyến 2 từ 1→4→3 (chi phí 4, 2 chặng) rồi chuyến 1 từ 3→2 (chi phí 3, 1 chặng). Tổng: 7 chi phí, 3 chặng.

Bình luận

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