Problem
Cho một đồ thị có hướng có thể có nhiều cạnh và nhiều vòng. Mỗi cạnh có trọng số được biểu thị dưới dạng số nguyên (có thể âm). Chúng tôi đảm bảo rằng không có chu kỳ trọng lượng âm.
Bạn cần tính độ dài của các đường đi ngắn nhất từ đỉnh số 1 đến tất cả các đỉnh khác.
Đầu vào
Đầu tiên chương trình nhận số N (1 <= N <= 100) – số đỉnh của đồ thị và số M (0 <= M <= 10000) – số lượng xương sườn. Các dòng tiếp theo chứa M bộ ba số mô tả các cạnh: đầu cạnh, cuối cạnh và trọng số (trọng lượng – là một số nguyên từ -100 đến 100).
Đầu ra
Chương trình sẽ xuất N số – khoảng cách từ đỉnh số 1 đến tất cả các đỉnh của đồ thị. Nếu không có đường đi đến đỉnh tương ứng, hãy in số 30000 thay vì độ dài của đường đi.
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
|
0 10 20 30000 30000 30000 |