class Solution:

    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:

        adj = [[] for _ in range(n)]

        dp = [0 for _ in range(n)]

        dp[start_node] = -1

        for i, (h, t) in enumerate(edges):

            adj[h].append((t, succProb[i]))

            adj[t].append((h, succProb[i]))

        heap = [(-1, start_node)]

        while heap:

            dist, prev = heappop(heap)

            if dp[prev] != dist:

                continue

            for nxt, prob in adj[prev]:

                if dp[prev] * prob < dp[nxt]:

                    dp[nxt] = dp[prev] * prob

                    heappush(heap, (dp[nxt], nxt))

        return abs(dp[end_node]) if dp[end_node] else 0

다익스트라 엄청 오랜만에 짜본다

안 보고 리마인드 할 수 있어서 다행