```
“”“
基本思想：
Floyd算法模板：
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(1, n+1): # 处理自环：正权边的自环一定不是最短路，所以初始化i到i的权重为0
graph[i][i] = 0

while m:
x,y,z = map(int, input().split())
graph[x][y] = min(graph[x][y], z) # 处理重边：保留重边中权重最小的边
m-=1
def Floyd():
for k in range(1,n+1):
for i in range(1, n+1):
for j in range(1,n+1):
graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j])
“”“
def Floyd():

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

if name==”main”:
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(1, n+1):    # 处理自环：正权边的自环一定不是最短路，所以初始化i到i的权重为0
    graph[i][i] = 0

while m:
    x,y,z = map(int, input().split())
    graph[x][y] = min(graph[x][y], z)    # 处理重边：保留重边中权重最小的边
    m-=1


Floyd()

while k:
    x, y = map(int, input().split())
    print("impossible") if graph[x][y]>= float("inf") else print(graph[x][y])
    k-=1

``