Cho đơn đồ thị có hướng $G = (N,E)$ với hàm trọng số $w: E → R$ $(w(e)$ được gọi là độ dài hay trọng số của cạnh e)

Đường đi ngắn nhất từ đỉnh $u$ đến đỉnh $v$ là đường đi có độ dài ngắn nhất trong số các đường đi nối $u$ với $v$.

Cho đồ thị có trọng số $G = (N, E)$ và đỉnh nguồn $S \in N$, hãy tìm đường đi ngắn nhất từ $S$ đến mỗi đỉnh còn lại.

• Dòng đầu chứa hai số nguyên $n$ và $m$ là số đỉnh và số cạnh của $G$.
• $m$ dòng tiếp theo, mỗi dòng chứa ba số số $u, v, c$ cho biết một cạnh nối hai đỉnh $u$ và $v$ trong $G$ và trọng số $c = w(u,v)$ tương ứng.
• Dòng cuối chứa 2 số nguyên $S$ và $F$ là đỉnh bắt đầu và đỉnh kết thúc.

• Trường hợp tìm thấy kết quả:

  • Dòng đầu ghi một số nguyên là tổng trọng số đường đi ngắn nhất.
  • Dòng thứ hai in ra đường đi ngắn nhất (mỗi đỉnh cách nhau một khoảng trống)

• Trường hợp không tìm ra đường đi thoả mãn, in ra -1

Lưu ý: Dữ liệu mẫu mang tính tham khảo. Bạn có thể in ra đường đi khác nhau nhưng vẫn đảm bảo có đường đi ngắn nhất