Tìm đường đi tối ưu

Trong một dự án tư vấn, FullHouse Dev đang phải đối mặt với một bài toán thú vị về tối ưu hóa chi phí di chuyển. Một chuyên gia tư vấn của công ty cần di chuyển giữa các thành phố và muốn tìm ra lộ trình tiết kiệm nhất có thể.

Bài toán

Một chuyên gia tư vấn có mức thu nhập \(K\) cho mỗi giờ làm việc. Anh ta cần bay từ thành phố A đến thành phố B với chi phí thấp nhất. Mỗi giờ di chuyển hoặc chờ đợi tại sân bay cho các chuyến bay nối chuyến, anh ta mất một khoản thu nhập \(K\). Giả sử thời gian chờ giữa các chuyến bay nối chuyến luôn là một giờ.

INPUT FORMAT:

• Dòng đầu tiên chứa số \(K\)
• Dòng thứ hai chứa số \(N\) - số lượng thành phố
• Dòng thứ ba chứa số \(X\) - số lượng tuyến đường giữa các thành phố
• \(X\) dòng tiếp theo, mỗi dòng chứa bốn số: số thành phố nguồn, số thành phố đích, thời gian bay và chi phí chuyến bay
• Dòng tiếp theo chứa \(S\) - thành phố xuất phát
• Dòng cuối cùng chứa \(D\) - thành phố đích

OUTPUT FORMAT:

In ra lộ trình tối ưu theo định dạng: \(S->[C1->C2->... ->Cy]->D\ T\ C\)

Trong đó:

• \(T\) là tổng thời gian (giờ)
• \(C\) là tổng chi phí (bao gồm cả chi phí cơ hội từ thu nhập bị mất)

Nếu không có đường đi khả thi hoặc vi phạm ràng buộc, in ra "Error".

Ví dụ

INPUT

1000
4
5
1 2 1 2500
1 3 1 3000
1 4 2 7000
2 4 1 3000
3 4 1 2000
1
4

OUTPUT

1->3->4 3 8000

Giải thích

Với lộ trình 1->3->4:

• Tổng thời gian = 3 giờ (1 giờ bay từ 1->3, 1 giờ chờ, 1 giờ bay từ 3->4)
• Tổng chi phí = 8000 (3000 cho chuyến 1->3, 2000 cho chuyến 3->4, 3000 cho thu nhập bị mất trong 3 giờ) Đây là lộ trình có tổng chi phí thấp nhất.