Đườ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

Đồ thị có trọng số, có hướng

Input

Dòng đầu gồm 3 số n,m,q trong đó n là số đỉnh của đồ thị, m là số cung (đường đi 1 chiều) và q là số truy vấn (1<n200;1mn(n1);1q105)

Tiếp theo gồm m dòng mỗi dòng gồm 3 giá trị u,v,w thể hiện cung (u,v) có trọng số w (1u,vu), u khác v; 1w104

Cuối cùng gồm q truy vấn mỗi truy vấn trên 1 dòng gồm hai đỉnh (u,v) (1u,vu), u khác v cần tính độ dài đường đi ngắn nhất

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 u đến đỉnh v trong trường hợp không có đường đi thì xuất ra 1

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
tichpx

Comments

There are no comments at the moment.