VOI 20 Bài 2 - Đi xe buýt - VNOJ: VNOI Online Judge

VOI 20 Bài 2 - Đi xe buýt

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.2s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Kỳ thi Học sinh giỏi Quốc gia 2020 - Ngày 1

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Đọc đề gốc tại đây.

Xe buýt là một phương tiện giao thông phổ biến tại thành phố mà Alice sinh sống bởi tính tiện dụng và giá cả hợp lý của nó. Thành phố có ~n~ bến xe buýt được đánh số từ ~1~ tới ~n~ và có ~m~ tuyến xe buýt hai chiều, mỗi tuyến đang được điều hành bởi một trong hai công ty vận tải ~A~ hoặc ~B~. Cụ thể, tuyến thứ ~i~ ~(1 \leq i \leq m)~ di chuyển giữa hai bến ~u_i~ và ~v_i~ với giá vé do công ty quản lý quy định là ~w_i~.

Lưu ý là giữa hai bến có thể có nhiều hơn một tuyến xe buýt.

Hai công ty ~A~ và ~B~ đều có chính sách giảm giá vé cho những ai thường xuyên đi bằng xe buýt. Cụ thể, mỗi ngày công ty ~A~ sẽ chỉ thu số tiền bằng với giá vé lớn nhất trong tất cả các tuyến được điều hành bởi công ty ~A~ mà khách hàng đã đi trong ngày. Để cạnh tranh, công ty ~B~ cũng có chính sách tương tự: khách hàng sẽ chỉ phải trả số tiền bằng giá vé lớn nhất trong tất cả các tuyến thuộc công ty ~B~ mà người đó đã đi trong ngày.

Nhà Alice ở gần bến xe buýt ~s~ và nơi làm của Alice ở gần bến xe buýt ~t~ nên hàng ngày Alice đều phải đi lại giữa hai bến này thông qua các tuyến xe buýt.

Yêu cầu: Bạn hãy giúp Alice xác định số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~.

Input

Dòng đầu tiên chứa bốn số nguyên dương ~n~, ~m~, ~s~ và ~t~ ~(n, m \leq 50\,000; \; s, t \leq n; \; s \neq t )~;
Dòng thứ ~i~ ~(1 \leq i \leq m)~ trong ~m~ dòng tiếp theo chứa bốn số nguyên dương ~c_i, u_i, v_i, w_i~ ~(u_i, v_i \leq n; \; u_i \neq v_i; \; w_i \leq 10^9)~ mô tả tuyến xe buýt thứ ~i~ trong đó ~c_i = 1~ nếu tuyến này được điều hành bởi công ty ~A~ hoặc ~c_i = 2~ nếu tuyến này được điều hành bởi công ty ~B~.

Các số trên cùng một dòng cách nhau bởi dấu cách. Dữ liệu đảm bảo luôn tồn tại cách đi lại giữa hai bến xe buýt ~s~ và ~t~ thông qua ~m~ tuyến xe.

Output

Ghi ra một số nguyên duy nhất là số tiền nhỏ nhất cần bỏ ra mỗi ngày để đảm bảo được việc đi từ bến xe buýt ~s~ đến bến xe buýt ~t~ cho Alice.

Giới hạn

Có ~20\%~ số lượng test ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: tất cả ~m~ tuyến xe buýt đều được điều hành bởi công ty ~A~;
~30\%~ số lượng test khác ứng với ~30\%~ số điểm của bài thỏa mãn điều kiện: ~n, m \leq 5\,000~;
~20\%~ số lượng test khác ứng với ~20\%~ số điểm của bài thỏa mãn điều kiện: tồn tại cách đi xe buýt tối ưu trong đó Alice chỉ sử dụng tối đa một tuyến xe của công ty ~B~;
~30\%~ số lượng test còn lại ứng với ~30\%~ số điểm của bài không có điều kiện gì thêm.

Sample Input

Sample Output

Note

Để đi từ ~1~ đến ~4~, Alice sẽ lần lượt đi tuyến ~(1~, ~2)~ của công ty ~A~ và hai tuyến ~(2~, ~5)~, ~(5~, ~4)~ của công ty ~B~. Khi đó số tiền mà Alice phải trả cho công ty ~A~ là ~4~ và trả cho công ty ~B~ là ~8~.

Bình luận

Hãy đọc nội quy trước khi bình luận.

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