使用BFS来求解有向的最短路径问题，主要路径有重合数据
import copy
class Solution:
    def findShortestPath(self , n: int, m: int, graph: List[List[int]]) -> int:
        # write code here
        
        data = graph
        graph = {}
        graph_value = {}
        whole_set = set()

        for x in data:
            if (x[0], x[1]) not in graph_value.keys():
                graph_value.update({(x[0], x[1]):x[2]})
            else:
                graph_value[(x[0],x[1])] = min(graph_value[(x[0],x[1])], x[2])
            if x[0] not in graph.keys():
                whole_set.add(x[0])
                graph.update({x[0]:[x[1]]})
            else:
                graph[x[0]].append(x[1])

        def solution():
            dp = [1000000 for i in range(n+1)]
            dp[1] = 0
            visited_set = set()
            visited_set.add(1)
            last_visited_set = set()
            
            while len(visited_set)>0:
                tp_visited_set = copy.deepcopy(visited_set)
                tp_tp_visited_set = set()
                for x in tp_visited_set:
                    if x in last_visited_set:
                        continue
                    last_visited_set.add(x)
                    if x in graph.keys():
                        d = graph[x]
                        for y in d:
                            # print(x, y, n, graph_value)
                            dp[y] = min(dp[y], dp[x] + graph_value[(x, y)])
                            tp_tp_visited_set.add(y)
                visited_set = copy.deepcopy(tp_tp_visited_set)

            return dp[n]

        return solution()