#1507 · Đường đi ngắn nhất

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