Đường Đi Ngắn Nhất Bellman-Ford

Buổi 41 — SPFA & Bellman-Ford
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Submissions
Đề bài

Cho một đồ thị có hướng gồm N đỉnh và M cạnh có trọng số (trọng số có thể âm). Dữ liệu đảm bảo đồ thị không chứa chu trình âm. Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh từ 1 đến N.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên N và M.
  • M dòng tiếp theo, mỗi dòng chứa ba số nguyên u, v, w mô tả cạnh có hướng từ u đến v với trọng số w.
Dữ liệu ra
  • In ra N giá trị trên một dòng, cách nhau bởi dấu cách. Giá trị thứ i là độ dài đường đi ngắn nhất từ 1 đến i, hoặc INF nếu không thể đi tới i từ 1.
Ví dụ
Input Output
4 5
1 2 4
1 3 5
2 3 -3
3 4 2
2 4 10
0 4 1 3
4 3
1 2 -2
2 3 5
1 3 10
0 -2 3 INF
Giới hạn
  • 1 ≤ N ≤ 1000
  • 0 ≤ M ≤ 5000
  • 1 ≤ u, v ≤ N
  • -10^6 ≤ w ≤ 10^6
Draft saved