iT邦幫忙

2021 iThome 鐵人賽

DAY 12
0
自我挑戰組

每日LeetCode解題紀錄系列 第 12

LeetCode解題 Day12

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

https://i.imgur.com/mI3j7lR.png


解法

  • 因為時間有點來不及,今天我就直接拿別人的解答來說明

這題雖然說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演算法


上一篇
LeetCode解題 Day11
下一篇
LeetCode解題 Day13
系列文
每日LeetCode解題紀錄30

尚未有邦友留言

立即登入留言