Thời Gian Gặp Mặt (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$ ô trên một trang trại, đánh số từ $1$ đến $N$ theo độ cao tăng dần. Có $M$ con đường một chiều từ ô số nhỏ hơn đến ô số lớn hơn. Hai người xuất phát đồng thời từ ô $1$ và cần đến ô $N$ vào đúng cùng một thời điểm. Mỗi con đường có chi phí riêng cho từng người.

Tìm thời gian tối thiểu để cả hai đến ô $N$ đồng thời, hoặc in IMPOSSIBLE nếu không thể.

Dữ liệu vào

Dòng đầu chứa $N$ và $M$ .

$M$ dòng tiếp theo, mỗi dòng có 4 số nguyên $A$ , $B$ , $C$ , $D$ ( $A < B$ ): con đường từ $A$ đến $B$ , người thứ nhất mất $C$ thời gian, người thứ hai mất $D$ thời gian.

Dữ liệu ra

Số nguyên là thời gian tối thiểu, hoặc IMPOSSIBLE.

Ràng buộc

$1 \leq N \leq 100$
$0 \leq M \leq \frac{N (N - 1)}{2}$
$1 \leq C, D \leq 100$

Ví dụ

Input	Output	Giải thích
3 3 1 3 1 2 1 2 1 2 2 3 1 2	2	Người 1 đi 1→2→3 hết 2, người 2 đi 1→3 hết 2. Cùng đến lúc 2.
4 6 1 3 1 1 3 4 2 4 1 4 1 1 1 2 4 2 2 3 4 2 2 4 3 5	1	Cả hai cùng đi 1→4 hết 1.

Bình luận

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