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

    solution

    Đề bài: [Giải thuật] Đường đi ngắn nhất Bellman-Ford và chu trình âm

    Cho đồ thị có hướng nnn đỉnh (đánh số từ 111) và mmm cạnh có trọng số (có thể âm). Từ đỉnh nguồn sss, hãy tính đường đi ngắn nhất tới mọi đỉnh.

    Với mỗi đỉnh vvv in ra:

    • Khoảng cách ngắn nhất nếu xác định.
    • INF nếu không tới được từ sss.
    • -INF nếu đường đi tới vvv có thể nhỏ tùy ý (bị ảnh hưởng bởi chu trình âm tới được từ sss).

    Ví dụ: với 333 đỉnh, 333 cạnh, nguồn 111 và các cạnh (1 2 5),(2 3 −2),(1 3 10)(1\,2\,5),(2\,3\,-2),(1\,3\,10)(125),(23−2),(1310) thì khoảng cách là 0 5 30\ 5\ 30 5 3.

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

      Dòng đầu: ba số nnn, mmm, sss. mmm dòng sau: mỗi dòng ba số uuu, vvv, www — cạnh có hướng từ uuu tới vvv trọng số www.

    • Ràng buộc đầu vào:

      1≤n≤20001 \le n \le 20001≤n≤2000, 0≤m≤60000 \le m \le 60000≤m≤6000, 1≤s≤n1 \le s \le n1≤s≤n, −104≤w≤104-10^4 \le w \le 10^4−104≤w≤104.

    • Định dạng đầu ra:

      Một dòng gồm nnn giá trị cách nhau bởi dấu cách: khoảng cách ngắn nhất từ sss tới đỉnh 1,2,…,n1,2,\dots,n1,2,…,n (hoặc INF/-INF).

    Ví dụ:

    Đầu vào:

    3 3 1
1 2 5
2 3 -2
1 3 10

    Đầu ra:

    0 5 3

    Giải thích:

    Đỉnh 1 cách 0; tới 2 trọng số 5; tới 3 qua 2 là 5+(-2)=3 < 10 nên chọn 3.

    Đang tải editor...