Hẹn Gặp

Đ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$ ô đồng được đánh số từ $1$ đến $N$ và $M$ con đường một chiều (chỉ đi từ ô số nhỏ sang ô số lớn). Mỗi con đường từ ô $A$ đến ô $B$ mất $C$ phút cho Bessie và $D$ phút cho Elsie.

Bessie và Elsie xuất phát đồng thời từ ô $1$ , cần đến ô $N$ vào cùng một thời điểm. Tìm thời gian nhỏ nhất để cả hai đến ô $N$ cùng lúc, hoặc in IMPOSSIBLE nếu không thể.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$ .

$M$ dòng tiếp theo, mỗi dòng chứa bốn số nguyên $A$ , $B$ , $C$ , $D$ — con đường từ ô $A$ đến ô $B$ mất $C$ phút cho Bessie, $D$ phút cho Elsie.

Dữ liệu ra

Thời gian nhỏ nhất (số nguyên), hoặc IMPOSSIBLE.

Ràng buộc

$1 \leq N \leq 16$
$M \leq N (N - 1) / 2$
$1 \leq C, D \leq 1000$
Với mọi con đường $A \to B$ : $A < B$

Ví dụ

Input	Output	Giải thích
3 3 1 3 1 2 1 2 1 2 2 3 1 2	2	Bessie đi 1→2→3 mất 1+1=2. Elsie đi thẳng 1→3 mất 2. Cả hai gặp nhau sau 2 phút.
4 6 3 4 122 774 2 3 629 47 2 4 958 1000 1 3 771 91 1 4 666 481 1 2 539 647	IMPOSSIBLE	Không tồn tại cặp đường nào cho cả hai đến ô 4 cùng lúc.

Bình luận

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