Cõng Bạn

Đ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

Có $N$ địa điểm và $M$ con đường hai chiều giữa chúng. Bessie xuất phát từ địa điểm $1$ , Elsie xuất phát từ địa điểm $2$ , cả hai cần đến địa điểm $N$ .

Khi di chuyển một mình, Bessie tốn $B$ năng lượng mỗi bước, Elsie tốn $E$ năng lượng mỗi bước.
Khi di chuyển cùng nhau (cõng nhau), cả hai tốn $P$ năng lượng mỗi bước (tổng cộng).

Chúng có thể gặp nhau tại bất kỳ địa điểm nào, rồi di chuyển cùng nhau về đích. Tìm tổng năng lượng tối thiểu để cả hai đến địa điểm $N$ .

Dữ liệu vào

Dòng đầu chứa năm số nguyên $B$ , $E$ , $P$ , $N$ , $M$ .

$M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ , $v$ — một con đường giữa địa điểm $u$ và $v$ .

Dữ liệu ra

Một số nguyên duy nhất — tổng năng lượng tối thiểu.

Ràng buộc

$1 \leq B, E, P, N, M \leq 40 000$
$N \geq 3$
Luôn tồn tại đường đi từ địa điểm $1$ và $2$ đến $N$

Ví dụ

Input	Output	Giải thích
4 4 5 8 8 1 4 2 3 3 4 4 7 2 5 5 6 6 8 7 8	22	Bessie đi 1→4 (1 bước, 4 năng lượng), Elsie đi 2→3→4 (2 bước, 8 năng lượng). Gặp nhau tại 4, cùng đi 4→7→8 (2 bước, 10 năng lượng). Tổng = 4+8+10 = 22.
3 2 1 10 9 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10	11	Bessie ở điểm 1, Elsie ở điểm 2, chúng gặp nhau tại điểm 1 hoặc 2, rồi cùng đi. Chi phí tối ưu = 11.

Bình luận

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