思路
1-初始设置源点的距离为0
2-更新n - 1次,每次更新找没有更新距离且距离源点最近的节点,用该节点更新所有点的距离
代码
n, m = map(int, input().split())
N = n + 1
g = [[float('inf')] * N for _ in range(N)] # 稠密图使用邻接矩阵进行存储, float('inf')可以用1 << 30 代替
dist = [float('inf')] * N
st = [False] * N
def dijkstra():
dist[1] = 0
for i in range(n - 1):
t = -1
# t---没有更新距离的节点中距离源点最近的点,然后用该点去更新其他点到源点的距离
for j in range(1, n + 1):
if not st[j] and (t == -1 or dist[t] > dist[j]):
t = j
for j in range(1, n + 1):
dist[j] = min(dist[j], dist[t] + g[t][j]) # 更新点t出去的边
st[t] = True
if dist[n] == float('inf'):
return -1
return dist[n]
for i in range(m):
a, b, c = map(int, input().split())
g[a][b] = min(g[a][b], c)
print(dijkstra())