摘要
Title: 849. Dijkstra求最短路 I
Tag: 最短路、Dijkstra
Memory Limit: 64 MB
Time Limit: 1000 ms

849. Dijkstra求最短路 I

题意

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。
思路

最短路汇总图，n代表点数，m代表边数
稠密图用邻接矩阵存，稀疏图用邻接表来存

朴素Dijkstra的板子

注意
- 要等全遍历完，再返回某点的最短路
- 当稠密图时，用朴素版的Dijkstra，用邻接矩阵存
- 当稀疏图时，用堆优化的Dijkstra,用邻接表存
$1≤n≤500,1≤m≤10^5$ 属于稠密图

代码

'''
Author: NEFU AB-IN
Date: 2022-03-02 22:20:20
FilePath: \ACM\Acwing\849.py
LastEditTime: 2022-03-02 23:21:42
'''
import heapq

N = int(1e3 + 10)
INF = int(2e9)
st, dist = [0] * N, [INF] * N
g = [[INF] * N for _ in range(N)]


def dij(s):
    dist[s] = 0
    for i in range(n - 1):  #循环n - 1次，因为已经选中了起点
        t = -1
        for j in range(1, n + 1):
            if st[j] == 0 and (t == -1 or dist[t] > dist[j]):  #每次挑出最小的点
                t = j
        st[t] = 1  #加入最短路
        for j in range(1, n + 1):  #用t点的最短路，更新j点的最短路
            dist[j] = min(dist[j], dist[t] + g[t][j])
    if dist[n] == INF:
        return -1
    return dist[n]


n, m = map(int, input().split())
for i in range(m):
    x, y, z = map(int, input().split())
    g[x][y] = min(g[x][y], z)  #可能出现重边，保留最短的那条边

print(dij(1))

849. Dijkstra求最短路 I

题意

思路

代码