Thiết kế mạng và đánh giá tuyến vận hành

Bối cảnh và bài toán

Một công ty có mạng đường vô hướng với chi phí xây dựng và thời gian di chuyển trên mỗi cạnh. Trước hết cần biết chi phí xây dựng cây khung rẻ nhất theo trường buildCost; đồng thời trên toàn mạng gốc cần tìm thời gian ngắn nhất từ s tới t theo travelTime.

Yêu cầu

In hai giá trị: MST build cost và shortest travel time. Nếu không có cây khung hoặc s không tới t thì vị trí tương ứng in -1.

Input

Dòng đầu n, m, s, t. Mỗi cạnh gồm u, v, buildCost, travelTime.

Output

In 'mstCost shortestTime'.

Ràng buộc

• 2 <= n <= 10^5
• 0 <= m <= 2*10^5
• 0 <= buildCost,travelTime <= 10^9 ## Chấm điểm | Subtask | Điểm | Điều kiện | Official tests | |---|---:|---|---| | S1 | 40 | n <= 200, m <= 500 (nếu có m) | 01–08 | | S2 | 60 | Không có ràng buộc bổ sung | 09–20 |

Ví dụ 1

Input

4 5 1 4
1 2 1 5
2 3 2 1
3 4 3 1
1 4 10 2
1 3 4 2

Output

6 2

Giải thích. Hai trường trọng số là hai mục tiêu độc lập nên cần MST theo buildCost và Dijkstra theo travelTime.

Ví dụ 2

Input

3 1 1 3
1 2 5 5

Output

-1 -1

Giải thích. Hai trường trọng số là hai mục tiêu độc lập nên cần MST theo buildCost và Dijkstra theo travelTime.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.