最大化一张图中的路径价值

标签: 图 数组 回溯

难度: Hard

给你一张 无向 图，图中有 n 个节点，节点编号从 0 到 n - 1 （都包括）。同时给你一个下标从 0 开始的整数数组 values ，其中 values[i] 是第 i 个节点的 价值 。同时给你一个下标从 0 开始的二维整数数组 edges ，其中 edges[j] = [uj, vj, timej] 表示节点 uj 和 vj 之间有一条需要 timej 秒才能通过的无向边。最后，给你一个整数 maxTime 。

合法路径 指的是图中任意一条从节点 0 开始，最终回到节点 0 ，且花费的总时间 不超过 maxTime 秒的一条路径。你可以访问一个节点任意次。一条合法路径的 价值 定义为路径中 不同节点 的价值 之和 （每个节点的价值 至多 算入价值总和中一次）。

请你返回一条合法路径的 最大 价值。

注意：每个节点 至多 有 四条 边与之相连。

示例 1：

输入：values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
输出：75
解释：
一条可能的路径为：0 -> 1 -> 0 -> 3 -> 0 。总花费时间为 10 + 10 + 10 + 10 = 40 <= 49 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 0 + 32 + 43 = 75 。

示例 2：

输入：values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30
输出：25
解释：
一条可能的路径为：0 -> 3 -> 0 。总花费时间为 10 + 10 = 20 <= 30 。
访问过的节点为 0 和 3 ，最大路径价值为 5 + 20 = 25 。

示例 3：

输入：values = [1,2,3,4], edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]], maxTime = 50
输出：7
解释：
一条可能的路径为：0 -> 1 -> 3 -> 1 -> 0 。总花费时间为 10 + 13 + 13 + 10 = 46 <= 50 。
访问过的节点为 0 ，1 和 3 ，最大路径价值为 1 + 2 + 4 = 7 。

示例 4：

输入：values = [0,1,2], edges = [[1,2,10]], maxTime = 10
输出：0
解释：
唯一一条路径为 0 。总花费时间为 0 。
唯一访问过的节点为 0 ，最大路径价值为 0 。

提示：

  • n == values.length
  • 1 <= n <= 1000
  • 0 <= values[i] <= 108
  • 0 <= edges.length <= 2000
  • edges[j].length == 3
  • 0 <= uj < vj <= n - 1
  • 10 <= timej, maxTime <= 100
  • [uj, vj] 所有节点对 互不相同 。
  • 每个节点 至多有四条 边。
  • 图可能不连通。

Submission

运行时间: 271 ms

内存: 62.2 MB

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        n = len(values)
        g = [[] for _ in range(n)]
        for a, b, t in edges:
            g[a].append((b, t))
            g[b].append((a, t))
        
        disFromStart = [inf] * n
        q = [(0, 0)]
        vis = set([0])
        while q:
            d, x = heappop(q)
            if disFromStart[x] < d: continue
            disFromStart[x] = d
            for y, c in g[x]:
                if disFromStart[y] > (newD := d + c):
                    disFromStart[y] = newD
                    heappush(q, (newD, y))

        total = sum(values)
        q = [(0, values[0], 0, 1)]  # (node, value, cost, visited)
        ans = -inf
        while q:
            tmp, q = q, []
            for node, val, cost, vis in tmp:
                if not node and val > ans:
                    ans = val
                    if ans == total: return ans
                for child, c in g[node]:
                    if (newCost := cost + c) <= maxTime - disFromStart[child]:
                        newVal = val + (vis >> child & 1 ^ 1) * values[child]
                        q.append((child, newVal, newCost, vis | (1 << child)))
        return ans

Explain

The problem is solved using a two-stage strategy. First, Dijkstra's algorithm is used to find the shortest distance from the start node (node 0) to all other nodes. This information is essential for the second part, where we search for the highest-value path. For the second stage, we employ a breadth-first search (BFS) approach using a queue to explore all possible paths from the start node that return to the start within the allowed time, recording the maximum value achieved by these paths. The BFS iterates over all possible moves from a node, checking the cost to ensure it does not exceed maxTime minus the shortest path to the return node. A bit-mask is used to keep track of visited nodes and to avoid counting a node's value more than once.

时间复杂度: O((n + e) log n + 2^n * n * e)

空间复杂度: O(n + e + 2^n * n)

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        n = len(values)
        g = [[] for _ in range(n)]
        for a, b, t in edges:
            g[a].append((b, t))
            g[b].append((a, t))

        disFromStart = [inf] * n
        q = [(0, 0)]
        while q:
            d, x = heappop(q)
            if disFromStart[x] < d: continue
            disFromStart[x] = d
            for y, c in g[x]:
                if disFromStart[y] > (newD := d + c):
                    disFromStart[y] = newD
                    heappush(q, (newD, y))

        total = sum(values)
        q = [(0, values[0], 0, 1)]
        ans = -inf
        while q:
            tmp, q = q, []
            for node, val, cost, vis in tmp:
                if not node and val > ans:
                    ans = val
                    if ans == total: return ans
                for child, c in g[node]:
                    if (newCost := cost + c) <= maxTime - disFromStart[child]:
                        newVal = val + (vis >> child & 1 ^ 1) * values[child]
                        q.append((child, newVal, newCost, vis | (1 << child)))
        return ans

Explore

在这个问题中，我们需要找到从起始节点返回到起始节点的最大价值路径，但同时需要确保路径的总时间不超过给定的最大时间（maxTime）。使用Dijkstra算法可以有效地找到从起始节点到图中任何其他节点的最短时间路径。这些信息是必要的，因为在后续的广度优先搜索（BFS）阶段，我们需要确保任何考虑的路径加上返回起始节点的时间总和不超过maxTime。因此，了解到每个节点的最短返回时间，可以帮助我们在BFS阶段有效地剪枝，排除那些无法在时间限制内返回起始节点的路径。

在BFS阶段，算法使用一个队列来迭代地探索从起始节点出发的所有可能路径。每次从队列中取出一个节点时，都会计算从该节点出发到任何可达子节点的新路径的总时间，并检查这个新路径的时间加上从该子节点返回起始节点的最短时间是否仍然在maxTime内。如果是，这条路径就被认为是有效的，并被加入到队列中以便进一步探索。通过这种方法，算法能够在确保时间限制的同时，尽可能地探索更多的路径，从而找到最大价值的路径。

在这个算法中使用bit-mask（位掩码）来跟踪已访问的节点是为了提高空间和时间效率。位掩码允许我们以非常紧凑的形式存储访问状态（每个节点仅占用一位），同时提供快速的访问和修改操作。相比之下，使用集合或字典虽然在理论上也可以实现相同的功能，但通常会占用更多的空间并可能导致较慢的查找和插入操作。特别是在节点数量较多的情况下，位掩码的效率优势更为明显。

在某些特殊情况下，如图形结构非常密集或图中存在许多低成本的边，算法的效率可能会降低。这是因为密集的图结构或低成本边会导致在BFS阶段产生大量的有效路径，使得队列迅速增大，增加了算法的空间和时间消耗。此外，如果图中的节点和边的数量非常大，Dijkstra算法和BFS阶段的时间复杂度也会显著增加，从而影响整体性能。因此，虽然这种策略在一般情况下表现良好，但在极端情况下可能需要考虑更高效的算法或优化措施。