星球游戏

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param serialP int一维数组 牛牛占领的p个星球的编号
# @param serialQ int一维数组 牛妹占领的q个星球的编号
# @param path int二维数组 m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
# @param nn int 星球个数n
# @return int
#
import collections,heapq
class Solution:
    def Length(self , serialP , serialQ , path , nn ):
        # write code here
        edges = collections.defaultdict(set)
        dis = {}
        p,q = set(),set()
        queue = []
        for x,y,v in path:
            if (x,y) in dis:
                dis[(x,y)] = min(dis[(x,y)],v)
                dis[(y,x)] = min(dis[(y,x)],v)
            else:
                edges[x].add(y)
                edges[y].add(x)
                dis[(x,y)] = v
                dis[(y,x)] = v
        for i in serialP:
            heapq.heappush(queue,[0,i])
            p.add(i)
        for i in serialQ:
            q.add(i)
        
        d = {}
        while queue:
            D,cur = heapq.heappop(queue)
            if cur in q:
                return D
            for next_ in edges[cur]:
                if (cur,next_) not in d&nbs***bsp;d[(cur,next_)] > D + dis[(cur,next_)]:
                    d[(cur,next_)] = D + dis[(cur,next_)]
                    heapq.heappush(queue,[d[(cur,next_)],next_])
        return -1