Number of Ways to Arrive at Destination

Ways compose over the shortest-path DAG — sum at equality.

The structural fact underneath: keep exactly the edges (u, v) satisfying dist[u] + w(u,v) = dist[v] — the 'tight' edges — and they form a DAG (dist strictly increases along each, so no cycles), whose source-to-v paths are IN BIJECTION with the shortest routes to v. Every shortest route uses only tight edges (a slack edge anywhere would overshoot the total), and every tight-edge path from the source totals exactly dist[v]. So ways[v] obeys clean DAG arithmetic: ways[source] = 1 (the empty route), and ways[v] = sum of ways[u] over tight in-edges — counts flowing forward through the DAG like Pascal's rule, because route sets through distinct predecessors are disjoint (different last edge) and exhaustive. Now the fusion that removes even the second pass: Dijkstra settles nodes in non-decreasing dist order, which is a valid topological order of the tight DAG — every tight predecessor of v settles before v (strictly smaller dist... with the equal-dist edge-weight-zero caveat absent here since weights are positive). So the sum can be accumulated DURING relaxation, and the two relaxation outcomes map exactly onto counting rules. Strict improvement (dist[u] + w < dist[v]): all previously counted routes to v just became non-shortest — obsolete — so OVERWRITE: ways[v] = ways[u]. Exact tie (dist[u] + w == dist[v]): a new family of shortest routes arriving via u, disjoint from those already counted (different final edge) — ADD: ways[v] += ways[u]. The overwrite-versus-add pair is the entire algorithm; everything else is Network Delay Time's engine unchanged. Two disciplines keep it honest. Modulo 1e9+7 on every addition — the counts are the exponential objects here even though the computation is polynomial, and they overflow fast. And only trust accumulations at SETTLED sources: with lazy-deletion Dijkstra, process a node's outgoing relaxations when it is popped fresh (first pop = settled = ways[u] final); adding from a node whose own count later grows would undercount downstream. The invariant to keep in your head: ways[v] is provisional until v settles, final after — mirroring dist[] exactly, which is why they can share one pass.