题目描述

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

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

输入格式
第一行包含整数n和m。

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

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

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

数据范围
1≤n≤500,
1≤m≤10^5,
图中涉及边长均不超过10000。

样例

输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3

算法1

Dijkstra求最短路 I

朴素Dijkstra
dist[1]=0,dist[i]=无穷
一开始只有1号点的距离是确定的，是0，其他点的距离是正无穷
之后迭代处理，确定一个点到起点的最短路（确定的是当前还没有确定的点中距离最小的点，基于贪心）
用邻接矩阵来存储图

python 代码

N = 10010   #最大长度，代替无穷
M = 510     #点


def dijkstra():
    #主函数里定义的变量，这里可以直接用
    dist[1] = 0
    for i in range(n):
        t = -1
        for j in range(1,n+1):
            if not st[j] and (t == -1 or dist[t] > dist[j]):    #找到没有确定最短路且距离最短的点。当前的点没有确定最短路 并且t==-1或当前的距离不是最短的
                t = j                                           #循环第一次找到第一个点
        st[t] = True                                            #t被确定为最短路点
        for j in range(1,n+1):
            dist[j] = min(dist[j],dist[t]+g[t][j])              #用确定的最短路的t更新其他点最短路的，1到t的距离+tj这条边


    if dist[n] == N:
        return -1
    return dist[n]



if __name__ == "__main__":

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

    g = [[N]*M for i in range(M)]     #稠密图用邻接矩阵写，稀疏图用邻接表
    for i in range(m):
        a,b,c = map(int,input().split())
        g[a][b] = min(g[a][b],c)    #a,b之间可能有多条边，只保留最短的那条就可以了
    print(dijkstra())