题目描述

给定一个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

算法1

Dijkstra求最短路 II

用堆优化。优化寻找t的过程

python 代码

import heapq
N = float('inf')   #最大长度，无穷
M = 150010     #点
e = [0] * M
ne = [0] * M
h = [-1] * M
w = [N] * M


def add(a, b,c):
    global idx  # idx在主函数里定义，但是动态变化，所以需要加global，数组不需要
    e[idx] = b
    ne[idx] = h[a]
    h[a] = idx
    w[idx] = c
    idx += 1

def dijkstra():
    #主函数里定义的变量，这里可以直接用
    dist[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))        #把1号点放进来，第一个位置是距离，第二个位置是编号
    while heap:
        d, node = heapq.heappop(heap)
        if st[node]:
            continue
        st[node] = True
        i = h[node]
        while i != -1:
            j = e[i]
            if dist[j] > dist[node] + w[i]:
                dist[j] = dist[node] + w[i]
                heapq.heappush(heap, (dist[j], j))
            i = ne[i]
    if dist[n] == N:
       return -1
    else:
       return dist[n]


if __name__ == "__main__":
    idx = 0
    dist = [N] * M      #存储从1号点到其他每个点的距离
    st = [False] * M    #存储每个点的最短路径是不是已经确定
    n,m = map(int,input().split())      #读入点数和边数


    for i in range(m):
        a,b,c = map(int,input().split())
        add(a,b,c)
    print(dijkstra())