题目描述
blablabla
样例
import math
if __name__ == "__main__":
n, m, k = map(int, input().split())
graph = [[math.inf] * n for _ in range(n)]
for i in range(n): graph[i][i] = 0
for i in range(m):
a, b, w = map(int, input().split())
a, b = a - 1, b - 1
graph[a][b] = min(graph[a][b], w)
for ne in range(n):
for i in range(n):
for j in range(n):
graph[i][j] = min(graph[i][j], graph[i][ne] + graph[ne][j])
for i in range(k):
a, b = map(int, input().split())
a, b = a - 1, b - 1
if graph[a][b] == math.inf:
print("impossible")
else:
print(graph[a][b])
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla