朴素Dijkstra

朴素Dijkstra算法适用于稠密图

数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）。

计算起点（第一个点）到终点（第n个点）的最短距离

# https://www.acwing.com/problem/content/description/851/
n, m = [int(x) for x in input().split(" ")]

# g 稠密图 使用邻接矩阵进行存储
g = [[float('inf')] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    a, b, w = [int(x) for x in input().split(" ")]
    g[a][b] = min(g[a][b], w)

# 每个点到起点的距离
dist = [float('inf')] * (n + 1)
# 起点为1号点
dist[1] = 0

# 该点的最短路是否已经确定
st = [False] * (n + 1)

for _ in range(n):
    # t 存储当前访问的点
    t = -1

    # 题目中点的标识从1开始
    for i in range(1, n + 1):
        if not st[i] and (t == -1 or dist[t] > dist[i]):
            t = i

    st[t] = True

    # 依次更新每个点到相邻点的路径值
    for i in range(1, n + 1):
        dist[i] = min(dist[i], dist[t] + g[t][i])

if dist[n] == float('inf'):
    print(-1)
else:
    print(dist[n])

# https://www.acwing.com/problem/content/description/851/
from collections import defaultdict

n, m = [int(x) for x in input().split(" ")]

dd = defaultdict(set)
for _ in range(m):
    a, b, w = [int(x) for x in input().split(" ")]
    dd[a].add((b, w))

# 每个点到起点的距离
dist = [float('inf')] * (n + 1)
# 起点为1号点
dist[1] = 0

# 该点的最短路是否已经确定
st = [False] * (n + 1)

for _ in range(n):
    # t 存储当前访问的点
    t = -1

    # 题目中点的标识从1开始
    for i in range(1, n + 1):
        if not st[i] and (t == -1 or dist[t] > dist[i]):
            t = i

    st[t] = True

    # 依次更新每个点到相邻点的路径值
    for b, w in dd[t]:
        dist[b] = min(dist[b], dist[t] + w)

if dist[n] == float('inf'):
    print(-1)
else:
    print(dist[n])