Introduction

In this blog post, we will explore how to solve the LeetCode problem "1976" 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

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that there is at most one road between any two intersections. You are given an integer n and a 2D integer array roads where roads[i] = [ui, vi, timei] means that there is a road between intersections ui and vi that takes timei minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n - 1 in the shortest amount of time. Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 109 + 7. Example 1: Input: n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]] Output: 4 Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes. The four ways to get there in 7 minutes are: - 0 ➝ 6 - 0 ➝ 4 ➝ 6 - 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6 - 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6 Example 2: Input: n = 2, roads = [[1,0,10]] Output: 1 Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes. Constraints: 1 <= n <= 200 n - 1 <= roads.length <= n * (n - 1) / 2 roads[i].length == 3 0 <= ui, vi <= n - 1 1 <= timei <= 109 ui != vi There is at most one road connecting any two intersections. You can reach any intersection from any other intersection.

Explanation

• Dijkstra's Algorithm: Use Dijkstra's algorithm to find the shortest time to reach each node from the starting node (node 0).
  • Path Counting: While running Dijkstra's, maintain a count of the number of shortest paths to each node. When a shorter path to a node is found, update the shortest time and reset the path count. If a path with the same shortest time is found, increment the path count.
  • Modulo Arithmetic: Apply modulo arithmetic to avoid integer overflow when counting paths.

• Runtime Complexity: O(E log V), where E is the number of roads and V is the number of intersections (nodes). Storage Complexity: O(V + E)

Code

    import heapq

def count_paths(n: int, roads: list[list[int]]) -> int:
    """
    Calculates the number of ways to travel from intersection 0 to intersection n - 1 in the shortest amount of time.

    Args:
        n: The number of intersections.
        roads: A list of roads, where roads[i] = [ui, vi, timei] represents a road between intersections ui and vi that takes timei minutes to travel.

    Returns:
        The number of ways to arrive at the destination in the shortest amount of time, modulo 10^9 + 7.
    """

    graph = [[] for _ in range(n)]
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))

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

    MOD = 10**9 + 7

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

        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            if dist[v] > dist[u] + weight:
                dist[v] = dist[u] + weight
                ways[v] = ways[u]
                heapq.heappush(pq, (dist[v], v))
            elif dist[v] == dist[u] + weight:
                ways[v] = (ways[v] + ways[u]) % MOD

    return ways[n - 1]