Cho một đồ thị có hướng gồm V đỉnh, được đánh số từ 0 đến V-1, và E cạnh. Mỗi cạnh (u, v) trong đồ thị có một trọng số w, biểu thị chi phí di chuyển từ đỉnh u đến đỉnh v. Trọng số w có thể là số âm.

Cho trước một đỉnh bắt đầu S.

Yêu cầu:

Sử dụng thuật toán Ford-Bellman để tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trong đồ thị.

Đầu vào:

• Dòng 1: Ba số nguyên V, E, S, lần lượt là số lượng đỉnh, số lượng cạnh, và đỉnh bắt đầu (0 <= S < V).
• E dòng tiếp theo: Mỗi dòng chứa ba số nguyên u, v, w, biểu thị một cạnh có hướng từ đỉnh u đến đỉnh v với trọng số w (0 <= u, v < V).

Đầu ra:

• Đối với mỗi đỉnh v từ 0 đến V-1, in ra đường đi ngắn nhất từ đỉnh S đến đỉnh v theo định dạng: "S -> v: trọng số".
  • Nếu không có đường đi từ S đến v, in ra: "S -> v: INF".
• Nếu đồ thị chứa chu trình âm, in ra thông báo: "Do thi co chu trinh am".