1

我使用元组集构建图形的以下代码将返回-1（解决方案存在但返回错误-1）：

def findCheapestPrice(self, n, flights, src, dst, K):
    """
    :type flights: List[List[int]]
    :type src: int
    :type dst: int
    :type K: int
    :rtype: int
    """

    # NOTE: Here I use a set
    g = collections.defaultdict(set)
    for s, d, cost in flights:
        g[s].add((cost, d))

    q, distance = [(0, 0, src)], {}
    heapq.heapify(q)
    while q:
        cost, stop, city = heapq.heappop(q)

        if stop>K+1 or cost>distance.get((stop, city), float('inf')): continue

        if city == dst:
            return cost
        for nbr, c in g.get(city, ()):
            if c+cost < distance.get((stop+1, nbr), float('inf')):
                distance[(stop+1, nbr)] = c+cost
                heapq.heappush(q, (c+cost, stop+1, nbr))
    return -1

但是，如果我将图形数据结构更改为 dict 的 dict，则代码可以工作。我已经彻底检查了差异，但仍然找不到答案。是什么导致了这些差异？

def findCheapestPrice(self, n, flights, src, dst, K):
    """
    :type flights: List[List[int]]
    :type src: int
    :type dst: int
    :type K: int
    :rtype: int
    """

    # NOTE: Here I use a dict
    g = collections.defaultdict(dict)
    for s, d, cost in flights:
        g[s][d]=cost

    q, distance = [(0, 0, src)], {}
    heapq.heapify(q)
    while q:
        cost, stop, city = heapq.heappop(q)

        if stop>K+1 or cost>distance.get((stop, city), float('inf')): continue

        if city == dst:
            return cost
        for nbr, c in g[city].items():
            if c+cost < distance.get((stop+1, nbr), float('inf')):
                distance[(stop+1, nbr)] = c+cost
                heapq.heappush(q, (c+cost, stop+1, nbr))
    return -1
4

1 回答 1

2 
g[s].add((cost, d))

这就是您在使用元组时初始化数据结构的方式。您可以使用 索引您的字典s，这是您的城市，您将输出一组元组。这些元组中的每一个都具有cost作为第一个元素。

当你像这样迭代它时：

for nbr, c in g.get(city, ()):

nbr是你的cost，因为它是你的元组中的第一个元素。

g[s][d]=cost

这是您在使用字典时初始化数据结构的方式。请记住，在这里您将cost其用作您的价值。

当你像这样迭代它时：

for nbr, c in g[city].items():

c是您的成本，因为nbr与密钥相关联，并且c与您的价值相关联，即成本。

总而言之nbr，c搞混了。在带有元组的变体中，成本被分配给nbr，而在带有字典的变体中，成本被分配给c。

于 2019-01-29T03:05:38.253 回答