Hai GPS Đối Đầu

Đ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

Xe của FJ có hai hệ thống GPS, mỗi hệ thống đánh giá thời gian di chuyển trên mỗi con đường khác nhau. FJ cần đi từ ngã tư $1$ (nhà) đến ngã tư $N$ (nông trại).

Khi FJ đi qua một con đường mà không nằm trên đường đi ngắn nhất (đến $N$ ) theo GPS nào đó, GPS đó sẽ phàn nàn 1 lần. Nếu cả hai GPS đều phàn nàn trên cùng một đường, tổng phàn nàn là 2.

Hãy tìm đường đi từ $1$ đến $N$ sao cho tổng số lần phàn nàn là nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo: mỗi dòng chứa $A_{i}$ , $B_{i}$ , $P_{i}$ , $Q_{i}$ — đường một chiều từ $A_{i}$ đến $B_{i}$ với thời gian $P_{i}$ theo GPS 1 và $Q_{i}$ theo GPS 2.

Dữ liệu ra

Một số nguyên duy nhất — tổng số lần phàn nàn tối thiểu.

Ràng buộc

$2 \leq N \leq 10 000$
$1 \leq M \leq 50 000$
$1 \leq P_{i}, Q_{i} \leq 100 000$
Có thể có nhiều đường nối cùng một cặp ngã tư.
Luôn tồn tại đường đi từ $1$ đến $N$ .

Ví dụ

Input	Output	Giải thích
5 7 3 4 7 1 1 3 2 20 1 4 17 18 4 5 25 3 1 2 10 1 3 5 4 14 2 4 6 5	1	Đi theo 1→2→4→5. Chỉ GPS 1 phàn nàn ở đoạn 1→2.

Bình luận

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