Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: Đường đi ngắn nhất

    Cho đồ thị có hướng gồm n đỉnh, m cạnh có trọng số dương. Tính khoảng cách ngắn nhất từ đỉnh 1 đến mọi đỉnh khác.

    • Định dạng đầu vào:
      • Dòng 1: n, m
      • m dòng: u, v, w (cạnh từ u đến v có trọng số w)
    • Định dạng đầu ra:

      Dòng 1: n số – khoảng cách từ 1 đến i (với i = 1..n, in 0 cho i=1, in -1 nếu không tới được).

    Ví dụ:

    Đầu vào:

    5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

    Đầu ra:

    0 2 3 9 6

    Đầu vào:

    3 1
1 2 5

    Đầu ra:

    0 5 -1

    Đầu vào:

    4 4
1 2 3
2 3 4
3 4 5
4 1 2

    Đầu ra:

    4 4
1 2 3
2 3 4
3 4 5
4 1 2

    Đầu vào:

    3 2
2 3 1
3 1 1

    Đầu ra:

    0 -1 -1

    Đang tải editor...