給出一個(gè)無向圖，每條邊有一個(gè)概率值，問從從start節(jié)點(diǎn)到end節(jié)點(diǎn)的所有path中概率值最大為多少（概率值為連乘關(guān)系）
1 #1514
2 #Runtime: 590 ms (Beats 94.20%)
3 #Memory: 26.2 MB (Beats 97.10%)
4
5 class Solution(object):
6 def kSmallestPairs(self, nums1, nums2, k):
7 """
8 :type nums1: List[int]
9 :type nums2: List[int]
10 :type k: int
11 :rtype: List[List[int]]
12 """
13 fg = set()
14 ans = []
15 hp = []
16 for i in range(min(len(nums1), k)):
17 heapq.heappush(hp, (nums1[i] + nums2[0], nums1[i], nums2[0], 0))
18 while k and hp:
19 _, i, j, idx = heapq.heappop(hp)
20 ans.append([i, j])
21 if idx < len(nums2) - 1:
22 heapq.heappush(hp, (i + nums2[idx + 1], i, nums2[idx + 1], idx + 1))
23 k -= 1
24 return ans