882. Reachable Nodes In Subdivided Graph

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/

题目解释

你有一个n 个点(node)组成的无向图original graph；接着，有若干个点把这无向图的边(edge)切开，标示如下: edges[i] = [ui, vi, cnti] 代表点ui 到点vi 的边之间插入了cnti 个点；最後，请回传点0 (node 0) 在距离maxMove 之内可以接触到几个点。

example

解法

• 因为时间有点来不及，今天我就直接拿别人的解答来说明

这题虽然说edge 之间有新增若干个点，不过我们可以把这些点当作weight，这样题目看起来就熟悉多了，就像是找最短路径的那种题目，而今天正是要用Dijkstra's 演算法。

不过Dijkstra's 还不足以解决这题，因为Dijkstra's 只会保留最短路径，而这题还另外要求在距离maxMove 内可以走到的点，那无向图的边就可能有以下几种可能:

1. 边是最短路径
2. 边长小於剩余的maxMove 但是不是最短路径
3. 边长大於剩余的maxMove

第一种状况用Dijkstra's 就可以把路径上的点算进来了；而第二第三种状况的边会被Dijkstra's 排除，则要另外把边长算进来，此外第三种状况的边还需要计算走到两侧还剩余多少maxMove。

不论如何都需要Dijkstra's 演算法，所以先上只有Dijkstra's 演算法的部分，也请参考看看Dijkstra's演算法的影片

Dijkstra's 演算法

class Solution(object):
    def reachableNodes(self, edges, M, N):
        graph = collections.defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w

        pq = [(0, 0)] # 等待计算距离的点 [distance, node]
        dist = {0: 0} # 纪录最短距离 {node: distance}

        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue

            for nei, weight in graph[node].items():
                d2 = d + weight + 1 # +1是因为点本身也占一步距离
                if d2 < dist.get(nei, math.inf):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2
                    # 更新最短路径

        print(dist)

接着是可以通过本题的解法

程序码

class Solution(object):
    def reachableNodes(self, edges, M, N):
        graph = collections.defaultdict(dict)
        for u, v, w in edges:
            graph[u][v] = graph[v][u] = w

        pq = [(0, 0)]
        dist = {0: 0}
        used = {}
        ans = 0

        while pq:
            d, node = heapq.heappop(pq)
            if d > dist[node]: continue
            ans += 1
            
            for nei, weight in graph[node].items():
                v = min(weight, M - d)
                used[node, nei] = v
                # min(weight, M - d)会把状况二、三的边长记下来
                # M - d代表到目前的点还剩多少步可以走，解决第三种状况

                d2 = d + weight + 1
                if d2 < dist.get(nei, M+1):
                    heapq.heappush(pq, (d2, nei))
                    dist[nei] = d2

        for u, v, w in edges:
            ans += min(w, used.get((u, v), 0) + used.get((v, u), 0))

        return ans

闲聊

Dijkstra真的很厉害，除了这个演算法外，他还有另一个知名的Banker's algorithm

但是他的名字太难记了，所以我都叫Dijkstra's 演算法为大DD演算法