Đường đi ngắn nhất - Thuật toán Floyd
Submit solution
Points:
4 (partial)
Time limit:
1.0s
Memory limit:
10M
Author:
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG
Cho đơn đồ thị G=(V,E) có hướng có trọng số ở cạnh và không có khuyên, hãy tìm đường đi ngắn nhất giữa các cặp đỉnh
Input
Dòng đầu gồm 3 số
Tiếp theo gồm
Cuối cùng gồm
Output
Với mỗi truy vấn xuất ra trên một dòng độ dài đường đi ngắn nhất từ đỉnh
Ví dụ
Input
Copy
6 10 5
1 2 16
1 4 14
3 1 7
2 3 7
3 4 2
4 5 8
3 5 12
2 6 4
3 6 2
5 6 5
1 6
6 3
3 5
4 2
2 5
Output
Copy
20
-1
10
-1
17
Comments