We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Arrive at Destination

Difficulty: Medium

Problem Description

You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. You are given an integer n and a 2D integer array roads where roads[i] = [u_i, v_i, time_i] means that there is a road between intersections u_i and v_i that takes time_i 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 modulo 10^9 + 7.

Key Insights

  • The problem can be modeled as a graph where intersections are nodes and roads are edges with weights representing travel time.
  • The goal is to find the shortest path from node 0 to node n - 1.
  • There may be multiple paths that yield the same shortest travel time, and we need to count all such distinct paths.
  • A combination of Dijkstra's algorithm for shortest path and dynamic programming to count paths can be utilized.

Space and Time Complexity

Time Complexity: O(E log V) where E is the number of edges and V is the number of vertices, due to the priority queue used in Dijkstra's algorithm.
Space Complexity: O(V + E) for storing the graph and additional structures for tracking distances and counts.

Solution

To solve this problem, we can use Dijkstra's algorithm to find the shortest path from the starting intersection to the destination. We will maintain an array to track the minimum time to reach each intersection and another array to count the number of ways to reach each intersection in that minimum time.

  1. Initialize a graph representation using an adjacency list.
  2. Create a priority queue to facilitate Dijkstra's algorithm.
  3. Use two arrays: one for the shortest times to each intersection and another for the count of ways to reach each intersection.
  4. Start from intersection 0, set its time to 0 and ways to 1.
  5. For each intersection processed, update its neighbors:
    • If a shorter path is found, update the shortest time and reset the count of ways.
    • If an equal shortest path is found, add to the count of ways.
  6. Finally, return the number of ways to reach intersection n - 1, modulo 10^9 + 7.

Code Solutions

import heapq
from collections import defaultdict

def countWays(n, roads):
    MOD = 10**9 + 7
    
    # Create a graph
    graph = defaultdict(list)
    for u, v, time in roads:
        graph[u].append((v, time))
        graph[v].append((u, time))

    # Dijkstra's algorithm
    min_time = [float('inf')] * n
    ways = [0] * n
    min_time[0] = 0
    ways[0] = 1
    pq = [(0, 0)]  # (time, node)

    while pq:
        curr_time, node = heapq.heappop(pq)

        for neighbor, time in graph[node]:
            new_time = curr_time + time
            if new_time < min_time[neighbor]:
                min_time[neighbor] = new_time
                ways[neighbor] = ways[node]
                heapq.heappush(pq, (new_time, neighbor))
            elif new_time == min_time[neighbor]:
                ways[neighbor] = (ways[neighbor] + ways[node]) % MOD

    return ways[n - 1]
← Back to All Questions