Hệ thống giao hàng có n điểm (0..n−1, đỉnh 0 là trung tâm). Ma trận g[i][j] là trọng số cạnh — g[i][j]=0 nghĩa không có cạnh từ i đến j (trừ đường chéo). Đồ thị vô hướng. Hãy in khoảng cách ngắn nhất từ 0 đến từng đỉnh 0..n−1 bằng Dijkstra; in −1 nếu không tới được.
Ví dụ ma trận 4×4 ở test mẫu cho dãy 0 1 3 4.
Dòng 1: n. Tiếp theo n dòng × n số nguyên không âm — ma trận trọng số.
1≤n≤50, 0≤g[i][j]≤104, g[i][i]=0.
Một dòng n số — khoảng cách từ đỉnh 0 tới từng đỉnh, cách nhau bởi dấu cách.
Ví dụ:
Đầu vào:
4
0 1 4 0
1 0 2 5
4 2 0 1
0 5 1 0
Đầu ra:
0 1 3 4
Giải thích:
Đang tải editor...