题解 | #单源最短路#

#设计状态数组vec=[999999]*(n+1)这里n+1是为了配合顶点为1~n,每个索引为1到这各顶点所需要的的最小步骤
#状态方程vec[j[1]]=min(vec[j[1]],vec[i]+j[2])为从上一点到达改点需要的步骤，与现在到达改点的最小步骤中的最小值
class Solution:
    def findShortestPath(self , n , m , graph ):
        # write code here
        vec=[999999999]*(n+1)
        vec[1]=0#初始化1到1为0
        for i in range(1,n+1):
            for j in graph:
                if j[0]==i:
                    vec[j[1]]=min(vec[j[1]],vec[i]+j[2])
        return vec[-1] if vec[-1]!=999999999 else -1