854. Floyd求最短路

发表于2022-03-03更新于2023-05-04字数统计417阅读时长3分阅读次数

摘要
Title: 854. Floyd求最短路
Tag: floyd、最短路、邻接矩阵
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

题意
思路
代码

854. Floyd求最短路

题意

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 impossible。
数据保证图中不存在负权回路。
思路

注意
- 当用邻接矩阵存图时
  - 处理重边：边取最小值，dist[x][y] = min(dist[x][y], z)
  - 处理自环：dist[i][i] = 0
  - 不存在解：dist[x][y] > INF // 2 因为邻接矩阵的遍历会遍历所有边，所以可能会有终点会被负权边更新，但与起点不通，所以还是无法到达的情况。所以只需判断最短路是否和INF一个量级即可
- 存图和距离的数组只需一个即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-03 15:45:54
FilePath: \ACM\Acwing\854.py
LastEditTime: 2022-03-03 16:01:18
'''
N = int(250)
INF = int(2e9)
dist = [[INF] * N for _ in range(N)]


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


n, m, q = map(int, input().split())
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            dist[i][j] = 0

for i in range(m):
    x, y, z = map(int, input().split())
    dist[x][y] = min(dist[x][y], z)

floyd()
for i in range(q):
    x, y = map(int, input().split())
    if dist[x][y] > INF // 2:
        print("impossible")
    else:
        print(dist[x][y])