Logistics (logistics.*)

Công ty Logistics Abela là một công ty thương mại điện tử lớn, chịu trách nhiệm tối ưu hóa các tuyến đường giao hàng phức tạp. Mỗi kiện hàng cần được vận chuyển từ kho chính (S) của công ty. Tuy nhiên, trước khi đến tay khách hàng cuối cùng (T), kiện hàng này bắt buộc phải ghé qua một trung tâm kiểm định (X) để kiểm tra chất lượng của sản phẩm.

Mạng lưới giao thông của thành phố rất rộng lớn, bao gồm nhiều tuyến đường nối các địa điểm quan trọng. Mỗi tuyến đường có một thời gian di chuyển cụ thể. Hãy tính toán thời gian di chuyển ngắn nhất cho toàn bộ quy trình giao nhận này. Điều đó có nghĩa là bạn cần tìm lộ trình nhanh nhất từ kho S đến trung tâm X, sau đó tiếp tục tìm lộ trình nhanh nhất từ trung tâm X đến điểm giao hàng T. Tổng thời gian của hai chặng đường này sẽ là tiêu chí then chốt để đảm bảo khách hàng nhận được hàng nhanh nhất và hiệu quả nhất.

Dữ liệu vào:

• Dòng 1: Năm số nguyên \(N,\ M,\ S,\ X,\ T\).

  • \(N\): Tổng số địa điểm trong mạng lưới giao hàng (đánh số từ 1 đến \(N\)).

  • \(M\): Số lượng tuyến đường kết nối các địa điểm.

  • \(S\): điểm xuất phát của kiện hàng.

  • \(X\): điểm dừng bắt buộc để xử lý hàng.

  • \(T\): điểm giao hàng cuối cùng.

• \(M\) dòng tiếp theo: Mỗi dòng gồm ba số nguyên \(U,\ V,\ W\).

  • \(U,\ V\): Hai địa điểm được kết nối bởi một tuyến đường.

  • \(W\): Thời gian di chuyển (trọng số) giữa \(U\) và \(V\).

Kết quả:

In ra tổng thời gian di chuyển ngắn nhất cho toàn bộ hành trình từ \(S \rightarrow X \rightarrow T\). Nếu không có đường đi hợp lệ nào để hoàn thành nhiệm vụ (ví dụ: không thể đến \(X\) từ \(S\), hoặc không thể đến \(T\) từ \(X\)), in ra \(- 1\).

Input	Output
6 8 1 4 6 1 2 5 1 3 10 2 4 8 3 4 2 4 5 3 4 6 7 5 6 4 2 3 1	15

Ràng buộc:

• \(1\ \leq \ N\ \leq \ 10^{3}\)

• \(1\ \leq \ S,\ T,\ X,\ U,\ V\ \leq \ N\)

• \(1\ \leq \ M\ \leq \ N \times (N - 1)/2\)

• \(1\ \leq \ W\ \leq \ 10^{9}\ \)