算法题 堆优化版本Dijkstra（Python）

题目：

给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。

输入格式

第一行包含整数n和m。

接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

如果路径不存在，则输出-1。

数据范围

1≤n,m≤1.5×10^5
图中涉及边长均不小于0，且不超过10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

代码：

from heapq import *

n, m = map(int, input().split())
idx = 0
h = [-1]*(n+1)
e, ne, w = [0]*(2*m+1), [0]*(2*m+1), [0]*(2*m+1)
st, dist = [False]*(n+1), [float('inf')]*(n+1)

def add(a, b, wei):
    global idx
    e[idx], w[idx] = b, wei
    h[a], ne[idx] = idx, h[a]
    idx += 1

def dijkstra():
    heap = []
    heappush(heap, [0, 1])
    dist[1] = 0
    while heap:
        d, cur_idx = heappop(heap)
        if st[cur_idx]: continue
        st[cur_idx] = True
        i = h[cur_idx]
        while i != -1:
            wei = w[i]
            t = e[i]
            if dist[t] > dist[cur_idx] + wei:
                dist[t] = dist[cur_idx] + wei
                heappush(heap, [dist[t], t])
            i = ne[i]
        
for _ in range(m):
    a, b, wei = map(int, input().split())
    add(a, b, wei)

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