单源最短路

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param n int 顶点数
# @param m int 边数
# @param graph int二维数组 一维3个数据，表示顶点到另外一个顶点的边长度是多少
# @return int
#
class Solution:
    def findShortestPath(self , n , m , graph ):
        def dijkstra(start, end):
            passed, nopass = [start], [x for x in range(len(adj)) if x != start]
            dis = adj[start]

            while len(nopass):
                idx = nopass[0]
                for i in nopass:
                    if dis[i] < dis[idx]: idx = i

                nopass.remove(idx)
                passed.append(idx)

                for i in nopass:
                    if dis[idx] + adj[idx][i] < dis[i]:
                        dis[i] = dis[idx] + adj[idx][i]
            return dis[end]
        adj = [[float("inf")]*(n) for _ in range(n)]
        for i in range(m):
            adj[graph[i][0]-1][graph[i][1]-1] = min(adj[graph[i][0]-1][graph[i][1]-1], graph[i][2])
        return dijkstra(0, n-1)

class Solution:
    def shortestPath(n, m, graph):
        dp = [-1 for _ in range(len(n) + 1)]
        dp[1] = 0
        minm = float("inf")
        for i in range(2, n+1):
            for j in range(m):
                if graph[j][1] == i and dp[graph[j][0]!=-1:
                    minm = min(minm, graph[j][2]+dp[graph[j][0]])
            dp[i] = minm if minm != float('inf') else -1
        return dp[n]

import sys
while True:
    try:
        line = sys.stdin.readline().rstrip().replace(" ", '')
        nm, graph = line.rstrip("]]").split(",[[")
        n, m = list(map(int, nm.split(",")))
        graph = grpah.split("],[")
        graph = [list(map(int, i.split(",")) for i in graph]
        s = Solution()
        print(s.shortestPath(n, m, graph))

    except:
        break