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

    solution

    Đề bài: [Mạng máy tính] Dijkstra: chi phí ngắn nhất từ nguồn

    Cho đồ thị vô hướng có trọng số dương: V đỉnh (0..V-1), E cạnh, và đỉnh nguồn s. Tính chi phí đường đi ngắn nhất từ s tới mọi đỉnh (Dijkstra). In V số trên một dòng cách nhau dấu cách: chi phí tới đỉnh 0,1,...,V-1. Nếu không tới được, in -1 cho đỉnh đó.

    • Định dạng đầu vào:

      Dòng 1: V E s. E dòng tiếp: u v w. In 1 dòng V số.

    Ví dụ:

    Đầu vào:

    3 3 0
0 1 4
1 2 1
0 2 10

    Đầu ra:

    0 4 5

    Giải thích:

    3 đỉnh, cạnh 0-1(4),1-2(1),0-2(10), nguồn 0: tới 0=0,1=4,2=5(qua 1).

    Đang tải editor...