Number of Ways to Arrive at Destination

There are n cities (0 .. n-1) connected by bidirectional roads roads[i] = [u, v, time]. Return the number of ways to travel from city 0 to city n-1 in the shortest possible time, modulo 10^9 + 7.

Hints

· Stuck? Reveal one nudge at a time.

Run Dijkstra, but also keep a count of shortest paths to each city.

On a strictly shorter time to v, reset ways[v] = ways[u].

On an equal time (a tie), add: ways[v] += ways[u], modulo 1e9+7.

Common doubts

A shorter time invalidates all previously-counted routes to v; only u's shortest routes now reach v optimally.

Vertices settle in non-decreasing distance, so every shortest-path predecessor of v has already contributed before v is finalised.

The number of shortest paths can grow exponentially; the modulus keeps it in range.

Interview follow-ups

· What an interviewer asks next.

Same idea with BFS: reset on a smaller level, accumulate on an equal level.

Store a parent on the first (strictly-better) relaxation, then backtrack.

Fun facts

LeetCode 1976 — Dijkstra plus a one-line counting DP.
The same reset/accumulate rule generalizes to counting shortest paths in any weighted graph.

Asked at

AmazonGoogle

Frequently Sometimes Occasionally

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
There are 4 distinct routes from 0 to 6 all achieving the shortest time 7.

Example 2

Input: n = 4, roads = [[0,1,1],[0,2,1],[1,3,1],[2,3,1]]
Output: 2
0→1→3 and 0→2→3 both take time 2.

Constraints

- 1 <= n <= 200 - 0 <= roads.length <= n*(n-1)/2 - 1 <= time <= 10^9 - no duplicate roads, no self-loops

This is Dijkstra with an extra bookkeeping array: alongside dist[v] (the shortest time to v), keep ways[v] (how many shortest-time routes reach v). Start with ways[0] = 1. When you relax an edge u → v with new time nd:

nd < dist[v] — a strictly better time: overwrite dist[v] and set ways[v] = ways[u] (all of u's shortest routes now extend to v).
nd == dist[v] — a tie: ways[v] += ways[u] (mod 10^9+7) — more distinct shortest routes reach v.

The answer is ways[n-1]. Everything else is standard Dijkstra (min-heap for O((V+E) log V), or a linear scan for O(V²)).

Prerequisites

Before you start

· Concepts used directly in the solution.

Dijkstra. shortest times from the source.

Path counting. accumulate ways on equal-distance relaxations.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Count all paths or shortest ones?”

Only the shortest-time paths.

“Why modulo?”

The count can be astronomically large.

The ideal opening — say it like this

I run Dijkstra but also carry a ways array: a strictly better time resets the count, a tie adds to it.

ways[n-1] modulo 1e9+7 is the answer.

Understand the problem

Worked example — n = 7, a graph with two equally-short routes 0→…→6

if two shortest paths reach 6 with the same total time, ways[6] = 2

Key observations

1Aha

Strictly better resets the count

ways[v] = ways[u].

2Aha

Tie accumulates the count

ways[v] += ways[u] (mod 1e9+7).

3Aha

Dijkstra's order finalises counts

Predecessors settle first, so ways[v] is complete when v settles.

Brute force vs optimal

	Dijkstra scan + count	Dijkstra heap + count
Find closest	linear scan	min-heap
Time	O(V²)	O((V+E) log V)
Counting	reset / accumulate	reset / accumulate

Both count the same number of shortest paths. Full code is in the Approaches selector below.

Summary

Key takeaway

Run Dijkstra with a ways[] array: strictly-better time resets ways[v] = ways[u]; a tie does ways[v] += ways[u] (mod 1e9+7). Answer is ways[n-1].

relax u->v: nd < dist[v] -> reset ways[v]=ways[u]; nd == dist[v] -> ways[v]+=ways[u]