Number of Ways to Arrive at Destination - Problem

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 10⁹ + 7.

Input & Output

Example 1 — Basic Graph

$ Input: n = 4, roads = [[0,1,1],[0,2,3],[1,3,2],[2,3,1]]

› Output: 1

💡 Note: There are two paths from 0 to 3: 0→1→3 (time 3) and 0→2→3 (time 4). Only one path has the shortest time of 3.

Example 2 — Multiple Shortest Paths

$ Input: n = 3, roads = [[0,1,1],[0,2,1],[1,2,1]]

› Output: 1

💡 Note: The shortest path from 0 to 2 is the direct path 0→2 with time 1. The path 0→1→2 has time 2, which is longer.

Example 3 — Single Path

$ Input: n = 2, roads = [[0,1,5]]

› Output: 1

💡 Note: Only one path from 0 to 1 with time 5, so count is 1.

Constraints

1 ≤ n ≤ 200
n - 1 ≤ roads.length ≤ n * (n - 1) / 2
roads[i].length == 3
0 ≤ u_i, v_i ≤ n - 1
1 ≤ time_i ≤ 10⁹
u_i != v_i

Visualization

Tap to expand

Asked in

G Google 15 f Facebook 12 a Amazon 8

Use Dijkstra's algorithm with path counting to find shortest paths while tracking the number of ways. The key insight is to modify Dijkstra to count paths: when finding a shorter path, reset count; when finding equal path, add to count. Time: O((V + E) log V), Space: O(V + E)

Common Approaches

✓ Brute Force DFS

⏱️ Time: O(2^n) Space: O(n)

Use depth-first search to explore all paths from intersection 0 to n-1, track the minimum time found, then count how many paths achieve this minimum time.

Dijkstra with Path Counting

⏱️ Time: O((V + E) log V) Space: O(V + E)

Modify Dijkstra's algorithm to not only find shortest distances but also count the number of shortest paths. When we find a shorter path, reset the count. When we find an equal path, add to the count.

Brute Force DFS — Algorithm Steps

DFS from source to find all paths
Track minimum time encountered
Count paths that match minimum time

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from intersection 0 with time 0

Explore Paths

Recursively try all neighbors, tracking current time

Count Minimum

Count paths that achieve minimum time to destination

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MOD 1000000007
#define MAX_N 200

typedef struct Edge {
    int to;
    long long time;
    struct Edge* next;
} Edge;

static Edge* graph[MAX_N];
static long long minTime;
static long long count;
static int visited[MAX_N];

void dfs(int node, int target, long long currentTime) {
    if (node == target) {
        if (currentTime < minTime) {
            minTime = currentTime;
            count = 1;
        } else if (currentTime == minTime) {
            count = (count + 1) % MOD;
        }
        return;
    }
    
    if (currentTime >= minTime) {
        return;
    }
    
    Edge* edge = graph[node];
    while (edge) {
        int neighbor = edge->to;
        long long time = edge->time;
        
        if (!visited[neighbor]) {
            visited[neighbor] = 1;
            dfs(neighbor, target, currentTime + time);
            visited[neighbor] = 0;
        }
        edge = edge->next;
    }
}

int solution(int n, int roads[][3], int roadsSize) {
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }
    
    for (int i = 0; i < roadsSize; i++) {
        int u = roads[i][0];
        int v = roads[i][1];
        int time = roads[i][2];
        
        Edge* e1 = (Edge*)malloc(sizeof(Edge));
        e1->to = v;
        e1->time = time;
        e1->next = graph[u];
        graph[u] = e1;
        
        Edge* e2 = (Edge*)malloc(sizeof(Edge));
        e2->to = u;
        e2->time = time;
        e2->next = graph[v];
        graph[v] = e2;
    }
    
    minTime = LLONG_MAX;
    count = 0;
    
    visited[0] = 1;
    dfs(0, n - 1, 0);
    
    for (int i = 0; i < n; i++) {
        Edge* edge = graph[i];
        while (edge) {
            Edge* temp = edge;
            edge = edge->next;
            free(temp);
        }
    }
    
    return (int)count;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int roads[1000][3];
    int roadsSize = 0;
    
    char* ptr = line;
    while (*ptr && roadsSize < 1000) {
        while (*ptr && (*ptr == '[' || *ptr == ' ' || *ptr == ',')) ptr++;
        if (*ptr == ']' || *ptr == '\n' || *ptr == '\0') break;
        
        int u, v, w;
        if (sscanf(ptr, "%d,%d,%d", &u, &v, &w) == 3) {
            roads[roadsSize][0] = u;
            roads[roadsSize][1] = v;
            roads[roadsSize][2] = w;
            roadsSize++;
        }
        
        while (*ptr && *ptr != ']') ptr++;
        if (*ptr == ']') ptr++;
    }
    
    int result = solution(n, roads, roadsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

In worst case, explores all possible paths which can be exponential

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n intersections

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Number of Ways to Arrive at Destination - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler