Đường đi ngắn nhất với Dijkstra
Cho đồ thị vô hướng liên thông có $N$ đỉnh và $M$ cạnh. Cạnh thứ $i$ nối hai đỉnh $u_i$ và $v_i$. Hãy tìm đường đi ngắn nhất từ đỉnh 1 đến tất cả các đỉnh còn lại sử dụng thuật toán Dijkstra.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, M \ (1\le N,M \le 10^5)$;
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i, v_i, w_i \ (1\le u_i, v_i \le N; u_i \neq v_i; 1\le w_i \le 10^4)$.
Dữ liệu đảm bảo không có hai cạnh nào chúng kết nối hai đỉnh.
Kết quả
- In ra $N-1$ số nguyên, lần lượt là đường đi ngắn nhất từ đỉnh 1 đến đỉnh $2, 3, 4, ..., N$.
Ví dụ
Ví dụ 1
input
5 6
1 3 3
2 4 2
3 5 5
2 3 4
1 5 4
4 5 1
output
7 3 5 4
Comments