python代码

def floyd() :
for i in range(1, n+ 1) :
for j in range(1, n + 1) :
for k in range(1, n + 1) :
graph[j][k] = min(graph[j][i] + graph[i][k], graph[j][k])

n, m, k = map(int, input().split())
graph = [[float(‘inf’) for i in range(n + 1)] for j in range (n + 1)]

for i in range(m) :
a, b, c = map(int, input().split())
graph[a][b] = min(graph[a][b], c)
for i in range(1, n + 1) :
graph[i][i] = 0

floyd()

for i in range(k) :
a, b = map(int, input().split())
if graph[a][b] == float(‘inf’) :
print(‘impossible’)
else :
print(graph[a][b])