Introduction

In this blog post, we will explore how to solve the LeetCode problem "1786" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There is an undirected weighted connected graph. You are given a positive integer n which denotes that the graph has n nodes labeled from 1 to n, and an array edges where each edges[i] = [ui, vi, weighti] denotes that there is an edge between nodes ui and vi with weight equal to weighti. A path from node start to node end is a sequence of nodes [z0, z1, z2, ..., zk] such that z0 = start and zk = end and there is an edge between zi and zi+1 where 0 <= i <= k-1. The distance of a path is the sum of the weights on the edges of the path. Let distanceToLastNode(x) denote the shortest distance of a path between node n and node x. A restricted path is a path that also satisfies that distanceToLastNode(zi) > distanceToLastNode(zi+1) where 0 <= i <= k-1. Return the number of restricted paths from node 1 to node n. Since that number may be too large, return it modulo 109 + 7. Example 1: Input: n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]] Output: 3 Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The three restricted paths are: 1) 1 --> 2 --> 5 2) 1 --> 2 --> 3 --> 5 3) 1 --> 3 --> 5 Example 2: Input: n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]] Output: 1 Explanation: Each circle contains the node number in black and its distanceToLastNode value in blue. The only restricted path is 1 --> 3 --> 7. Constraints: 1 <= n <= 2 104 n - 1 <= edges.length <= 4 104 edges[i].length == 3 1 <= ui, vi <= n ui != vi 1 <= weighti <= 105 There is at most one edge between any two nodes. There is at least one path between any two nodes.

Explanation

Here's a breakdown of the solution approach, followed by the Python code.

• Calculate Shortest Distances to the Last Node: Use Dijkstra's algorithm to find the shortest distance from each node to node n. This gives us distanceToLastNode(x) for all nodes x.
• Dynamic Programming with Memoization: Compute the number of restricted paths from node 1 to node n using dynamic programming. The key idea is to only consider paths where the distanceToLastNode decreases at each step. Memoize the results to avoid redundant calculations.

• Topological Sort (Implicit): The dynamic programming approach, guided by the decreasing distanceToLastNode values, implicitly performs a topological sort of the graph based on these distances.

• Runtime Complexity: O(E log V), where E is the number of edges and V is the number of vertices (nodes). This is dominated by Dijkstra's algorithm. The DP part is O(E) as each edge is visited at most once.

• Storage Complexity: O(V + E), primarily due to the adjacency list representation of the graph, the dist array for Dijkstra, and the dp array for memoization.

Code

    import heapq

def countRestrictedPaths(n: int, edges: list[list[int]]) -> int:
    """
    Counts the number of restricted paths from node 1 to node n in a graph.

    Args:
        n: The number of nodes in the graph.
        edges: A list of edges, where each edge is a tuple (u, v, weight).

    Returns:
        The number of restricted paths modulo 10^9 + 7.
    """

    adj = [[] for _ in range(n + 1)]
    for u, v, weight in edges:
        adj[u].append((v, weight))
        adj[v].append((u, weight))

    dist = dijkstra(n, adj)
    dp = {}  # Memoization for dynamic programming

    def dfs(node):
        if node == n:
            return 1
        if node in dp:
            return dp[node]

        count = 0
        for neighbor, _ in adj[node]:
            if dist[node] > dist[neighbor]:
                count = (count + dfs(neighbor)) % (10**9 + 7)

        dp[node] = count
        return count

    return dfs(1)


def dijkstra(n: int, adj: list[list[tuple[int, int]]]) -> list[int]:
    """
    Calculates the shortest distance from each node to node n using Dijkstra's algorithm.

    Args:
        n: The number of nodes in the graph.
        adj: The adjacency list representation of the graph.

    Returns:
        A list of shortest distances from each node to node n.
    """

    dist = [float('inf')] * (n + 1)
    dist[n] = 0
    pq = [(0, n)]  # (distance, node)

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in adj[u]:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))

    return dist