LeetCode - Dijkstra

Posted on Edited on In

See 两种 Dijkstra 写法（附题单）Python/Java/C++/Go/JS/Rust.

743. Network Delay Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for x, y, d in times:
            g[x - 1].append((y - 1, d))
        dis = [inf] * n
        dis[k - 1] = 0
        h = [(0, k - 1)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx + d
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
        mx = max(dis)
        return mx if mx < inf else -1

2642. Design Graph With Shortest Path Calculator

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Graph:

    def __init__(self, n: int, edges: List[List[int]]):
        g = [[] for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
        self.g = g

    def addEdge(self, edge: List[int]) -> None:
        self.g[edge[0]].append((edge[1], edge[2]))

    def shortestPath(self, node1: int, node2: int) -> int:
        n = len(self.g)
        dis = [inf] * n
        dis[node1] = 0
        h = [(0, node1)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, d in self.g[x]:
                new_dis = dx + d
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
        return dis[node2] if dis[node2] < inf else -1

1514. Path with Maximum Probability

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxProbability(self, n: int, edges: List[List[int]], succProb: List[float], start_node: int, end_node: int) -> float:
        g = [[] for _ in range(n)]
        for i, (a, b) in enumerate(edges):
            g[a].append((b, succProb[i]))
            g[b].append((a, succProb[i]))
        dis = [0] * n
        dis[start_node] = 1
        h = [(-1, start_node)]
        while h:
            dx, x = heappop(h)
            dx = -dx
            if dx < dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx * d
                if new_dis > dis[y]:
                    dis[y] = new_dis
                    heappush(h, (-new_dis, y))
        return dis[end_node]

1631. Path With Minimum Effort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m, n = len(heights), len(heights[0])
        h = [(0, 0, 0)]
        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = 0
        while h:
            d, x, y = heappop(h)
            if x == m - 1 and y == n - 1:
                return d
            if d > dis[x][y]:
                continue
            for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= nx < m and 0 <= ny < n:
                    new_dis = max(d, abs(heights[nx][ny] - heights[x][y])) 
                    if new_dis < dis[nx][ny]:
                        dis[nx][ny] = new_dis
                        heappush(h, (new_dis, nx, ny))
        return -1

1368. Minimum Cost to Make at Least One Valid Path in a Grid

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def minCost(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dis = [[inf] * n for _ in range(m)]
        dis[0]
        h = [(0, 0, 0)]
        while h:
            d, x, y = heappop(h)
            if x == m - 1 and y == n - 1:
                return d
            for num, (nx, ny) in zip([1, 2, 3, 4], [(x, y + 1), (x, y - 1), (x + 1, y), (x - 1, y)]):
                if 0 <= nx < m and 0 <= ny < n:
                    new_dis = d if num == grid[x][y]  else d + 1
                    if new_dis < dis[nx][ny]:
                        dis[nx][ny] = new_dis
                        heappush(h, (new_dis, nx, ny))

1786. Number of Restricted Paths From First to Last Node

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for x, y, d in edges:
            g[x].append((y, d))
            g[y].append((x, d))
        dis = [inf] * (n + 1)
        dis[n] = 0
        h = [(0, n)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx + d
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
        if dis[1] == inf:
            return 0
        mem = {n:1}
        mod = 10**9 + 7
        def dfs(root):
            if root in mem:
                return mem[root]
            mem[root] = 0
            for v, _ in g[root]:
                if dis[root] > dis[v]:
                    mem[root] = (mem[root] + dfs(v)) % mod
            return mem[root]
        return dfs(1)

1976. Number of Ways to Arrive at Destination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        g = [[] for _ in range(n)]
        for x, y, d in roads:
            g[x].append((y, d))
            g[y].append((x, d))
        dis = [inf] * n
        dis[0] = 0
        f = [0] * n
        f[0] = 1
        h = [(0, 0)]
        while True:
            dx, x = heappop(h)
            if x == n - 1:
                return f[-1]
            if dx > dis[x]:
                continue
            for y, d in g[x]:
                new_dis = dx + d
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    f[y] = f[x]
                    heappush(h, (new_dis, y))
                elif new_dis == dis[y]:
                    f[y] = (f[y] + f[x]) % 1_000_000_007

2662. Minimum Cost of a Path With Special Roads

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minimumCost(self, start: List[int], target: List[int], specialRoads: List[List[int]]) -> int:
        t = tuple(target)
        dis = defaultdict(lambda: inf)
        dis[tuple(start)] = 0
        vis = set()
        while True:
            v, dv = None, -1
            for p, d in dis.items():
                if p not in vis and (dv < 0 or d < dv):
                    v, dv = p, d
            if v == t:
                return dv
            vis.add(v)
            vx, vy = v
            dis[t] = min(dis[t], dv + t[0] - vx + t[1] - vy)
            for x1, y1, x2, y2, cost in specialRoads:
                w = (x2, y2)
                dis[w] = min(dis[w], dv + abs(x1 - vx) + abs(y1 - vy) + cost)

2045. Second Minimum Time to Reach Destination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        g = [[] for _ in range(n + 1)]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        dis = [[inf] * 2 for _ in range(n + 1)]
        dis[1][0] = 0
        q = deque([(1, 0)])
        while dis[n][1] == inf:
            x, dx = q.popleft()
            for y in g[x]:
                d = dx + 1
                if d < dis[y][0]:
                    dis[y][0] = d
                    q.append((y, d))
                elif dis[y][0] < d < dis[y][1]:
                    dis[y][1] = d
                    q.append((y, d))
        ans = 0
        for _ in range(dis[n][1]):
            if ans % (change * 2) >= change:
                ans += change * 2 - ans % (change * 2)
            ans += time
        return ans

882. Reachable Nodes In Subdivided Graph

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
        g = [[] for _ in range(n)]
        for u, v, cnt in edges:
            g[u].append((v, cnt + 1))
            g[v].append((u, cnt + 1))
        dis = self.dijkstra(g, 0)
        ans = sum(d <= maxMoves for d in dis)
        for u, v, cnt in edges:
            a = max(maxMoves - dis[u], 0)
            b = max(maxMoves - dis[v], 0)
            ans += min(a + b, cnt)
        return ans

    def dijkstra(self, g: List[List[Tuple[int]]], start: int) -> List:
        dis = [inf] * len(g)
        dis[start] = 0
        h = [(0, start)]
        while h:
            dx, x = heappop(h)
            if dx > dis[x]:
                continue
            for y, w in g[x]:
                new_dis = dis[x] + w
                if new_dis < dis[y]:
                    dis[y] = new_dis
                    heappush(h, (new_dis, y))
        return dis

2203. Minimum Weighted Subgraph With the Required Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        def dijkstra(g: List[List[Tuple[int]]], start: int) -> List[int]:
            dis = [inf] * n
            dis[start] = 0
            h = [(0, start)]
            while h:
                dx, x = heappop(h)
                if dx > dis[x]:
                    continue
                for y, w in g[x]:
                    new_dis = dis[x] + w
                    if new_dis < dis[y]:
                        dis[y] = new_dis
                        heappush(h, (new_dis, y))
            return dis
        
        g = [[] for _ in range(n)]
        rg = [[] for _ in range(n)]
        for x, y, w in edges:
            g[x].append((y, w))
            rg[y].append((x, w))

        d1 = dijkstra(g, src1)
        d2 = dijkstra(g, src2)
        d3 = dijkstra(rg, dest)

        ans = min(sum(d) for d in zip(d1, d2, d3))
        return ans if ans < inf else -1

2577. Minimum Time to Visit a Cell In a Grid

See 两种方法：Dijkstra/二分答案+BFS（Python/Java/C++/Go）.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def minimumTime(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if grid[0][1] > 1 and grid[1][0] > 1:
            return -1 # no wait, no way.
        dis = [[inf] * n for _ in range(m)]
        dis[0][0] = 0
        h = [(0, 0, 0)]
        while h:
            d, x, y = heappop(h)
            if d > dis[x][y]:
                continue
            if x == m - 1 and y == n - 1:
                return d
            for nx, ny in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
                if 0 <= nx < m and 0 <= ny < n:
                    new_dis = max(d + 1, grid[nx][ny])
                    new_dis += (new_dis - nx - ny) % 2 # parity contraint.
                    if new_dis < dis[nx][ny]:
                        dis[nx][ny] = new_dis
                        heappush(h, (new_dis, nx, ny))

2699. Modify Graph Edge Weights

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
    def modifiedGraphEdges(self, n: int, edges: List[List[int]], source: int, destination: int, target: int) -> List[List[int]]:
        g = [[] for _ in range(n)]
        for i, (x, y, _) in enumerate(edges):
            g[x].append((y, i))
            g[y].append((x, i))
        dis = [[inf, inf] for _ in range(n)]
        dis[source] = [0, 0]

        def dijkstra(k: int) -> None:
            vis = [False] * n
            while True:
                x = -1
                for y, (b, d) in enumerate(zip(vis, dis)):
                    if not b and (x < 0 or d[k] < dis[x][k]):
                        x = y
                if x == destination:
                    return
                vis[x] = True
                for y, eid in g[x]:
                    wt = edges[eid][2]
                    if wt == -1:
                        wt = 1
                    if k == 1 and edges[eid][2] == -1:
                        w = delta + dis[y][0] - dis[x][1]
                        if w > wt:
                            edges[eid][2] = wt = w
                    dis[y][k] = min(dis[y][k], dis[x][k] + wt)

        dijkstra(0)
        delta = target - dis[destination][0]
        if delta < 0:
            return []
        
        dijkstra(1)
        if dis[destination][1] < target:
            return []
        
        for e in edges:
            if e[2] == -1:
                e[2] = 1
        return edges