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

    solution

    Đề bài: [Giải thuật] Khoảng cách mọi cặp đỉnh Floyd-Warshall

    Cho đồ thị có hướng nnn đỉnh, mmm cạnh trọng số không âm. Tính khoảng cách ngắn nhất giữa mọi cặp đỉnh, sau đó trả lời qqq truy vấn: khoảng cách ngắn nhất từ aaa tới bbb.

    Nếu không có đường đi, in INF. Nếu có nhiều cạnh giữa cùng cặp đỉnh, dùng cạnh nhỏ nhất.

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

      Dòng đầu: nnn, mmm. mmm dòng: uuu, vvv, www. Dòng kế: qqq. qqq dòng: aaa, bbb.

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

      1≤n≤4001 \le n \le 4001≤n≤400, 0≤m≤n(n−1)0 \le m \le n(n-1)0≤m≤n(n−1), 0≤w≤1060 \le w \le 10^60≤w≤106, 1≤q≤1041 \le q \le 10^41≤q≤104.

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

      qqq dòng, mỗi dòng là khoảng cách a→ba\to ba→b hoặc INF.

    Ví dụ:

    Đầu vào:

    3 3
1 2 5
2 3 2
1 3 100
2
1 3
3 1

    Đầu ra:

    7
INF

    Giải thích:

    Cạnh: (1->2:5),(2->3:2),(1->3:100). Đường 1->2->3 = 7 < 100. Từ 3 không có đường về 1 nên INF.

    Đang tải editor...