Độ khó: Khó (4/4 điểm)

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Vùng sông nước có ~N~ bến, đánh số từ ~1~ đến ~N~, và ~M~ tuyến đường hai chiều nối các bến. Tuyến thứ ~i~ nối hai bến ~u_i, v_i~ và đi hết ~w_i~ phút. Có hai loại tuyến:

• Nếu ~p_i = 0~: đây là đường bộ, có thể xuất phát bất cứ lúc nào.
• Nếu ~p_i > 0~: đây là tuyến phà. Phà (theo cả hai chiều) chỉ rời bến vào các thời điểm ~0, p_i, 2p_i, 3p_i, \dots~ Nếu đến bến lúc ~t~ mà muốn đi phà thì phải chờ tới thời điểm rời bến sớm nhất không nhỏ hơn ~t~.

Thầy Sơn xuất phát từ bến ~1~ ở thời điểm ~0~ và cần tới bến ~N~ càng sớm càng tốt. Thầy Sơn có ~K~ vé ưu tiên: khi dùng một vé cho một lần đi phà, phà rời bến ngay lúc thầy Sơn tới (không phải chờ). Mỗi vé chỉ dùng được một lần. Thầy Sơn được phép đi qua một bến hay một tuyến nhiều lần.

Hãy tính thời điểm sớm nhất thầy Sơn tới được bến ~N~.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~N, M, K~ ~(2 \le N \le 10^5;\ 1 \le M \le 2 \times 10^5;\ 0 \le K \le 5)~.
• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa bốn số nguyên ~u_i, v_i, w_i, p_i~ ~(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 1 \le w_i \le 10^9;\ 0 \le p_i \le 10^9)~. Giữa hai bến có thể có nhiều tuyến.

Kết quả

Một số nguyên duy nhất là thời điểm sớm nhất tới bến ~N~. Nếu không thể tới được, in ra -1.

Giới hạn (Subtask)

• Subtask 1 (~20\%~ số điểm): mọi ~p_i = 0~.
• Subtask 2 (~30\%~ số điểm): ~K = 0~.
• Subtask 3 (~50\%~ số điểm): không có ràng buộc gì thêm.

💡 Lưu ý khi nộp bằng Python: các em nên chọn ngôn ngữ PyPy 3 thay vì Python 3 để chương trình chạy nhanh hơn nhiều. Giới hạn thời gian cho Python/PyPy ở bài này là 5 giây.

Sample Input 1

4 4 0
1 2 2 0
2 4 3 4
1 3 1 0
3 4 7 0

Sample Output 1

7

Sample Input 2

4 4 1
1 2 2 0
2 4 3 4
1 3 1 0
3 4 7 0

Sample Output 2

5

Giải thích

• Ví dụ 1: đi bộ ~1 \to 2~ tới lúc ~2~, chờ phà ~2 \to 4~ rời bến lúc ~4~, tới bến ~4~ lúc ~7~. Đi đường ~1 \to 3 \to 4~ cũng tới lúc ~1 + 7 = 8~, chậm hơn.
• Ví dụ 2: tới bến ~2~ lúc ~2~ thì dùng vé ưu tiên, phà rời bến ngay, tới bến ~4~ lúc ~5~.

Nguồn: Đề tự luyện HSG Tin học lớp 12 (đề tự soạn).