1976. Number of Ways to Arrive at Destination

At a Glance

Topic: graphs
Pattern: Dijkstra + counting (shortest-path family)
Difficulty: Medium
Companies: Amazon, Google, Microsoft, Meta, Bloomberg
Frequency: Medium
LeetCode: 1976

Problem (one-liner)

Undirected weighted roads between intersections 0..n-1. Count how many distinct shortest-time routes from 0 to n-1 modulo 1e9+7.

Recognition Cues

Count paths achieving minimum total weight — relax like Dijkstra; accumulate ways when strictly improving distance; add ways when tie distance

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Enumerate all shortest paths — exponential — bad.
Optimal — one Dijkstra tracking distance[] and ways[] — O((V+E) log V).

Optimal Solution

Go

import (
	"container/heap"
)

const modulo = 1000000007

type roadEdge struct {
	target int
	time   int
}

type state struct {
	node     int
	distance int
}

type stateHeap []state

func (heapSlice stateHeap) Len() int { return len(heapSlice) }
func (heapSlice stateHeap) Less(left, right int) bool {
	return heapSlice[left].distance < heapSlice[right].distance
}
func (heapSlice stateHeap) Swap(left, right int) {
	heapSlice[left], heapSlice[right] = heapSlice[right], heapSlice[left]
}

func (heapSlice *stateHeap) Push(value any) {
	*heapSlice = append(*heapSlice, value.(state))
}

func (heapSlice *stateHeap) Pop() any {
	old := *heapSlice
	length := len(old)
	item := old[length-1]
	*heapSlice = old[0 : length-1]
	return item
}

func countPaths(nodeCount int, roads [][]int) int {
	graph := make([][]roadEdge, nodeCount)
	for _, row := range roads {
		left := row[0]
		right := row[1]
		travel := row[2]
		graph[left] = append(graph[left], roadEdge{target: right, time: travel})
		graph[right] = append(graph[right], roadEdge{target: left, time: travel})
	}
	distances := make([]int, nodeCount)
	for index := range distances {
		distances[index] = 1 << 60
	}
	ways := make([]int, nodeCount)
	distances[0] = 0
	ways[0] = 1
	minHeap := &stateHeap{}
	heap.Init(minHeap)
	heap.Push(minHeap, state{node: 0, distance: 0})

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(state)
		if current.distance > distances[current.node] {
			continue
		}
		for _, neighbor := range graph[current.node] {
			nextDistance := current.distance + neighbor.time
			if nextDistance < distances[neighbor.target] {
				distances[neighbor.target] = nextDistance
				ways[neighbor.target] = ways[current.node]
				heap.Push(minHeap, state{node: neighbor.target, distance: nextDistance})
			} else if nextDistance == distances[neighbor.target] {
				ways[neighbor.target] = (ways[neighbor.target] + ways[current.node]) % modulo
			}
		}
	}
	return ways[nodeCount-1]
}

JavaScript

const MODULO = 1000000007;

class MinHeap {
  constructor() {
    this.data = [];
  }

  size() {
    return this.data.length;
  }

  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }

  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }

  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index].distance >= this.data[parentIndex].distance) {
        break;
      }
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  bubbleDown(index) {
    const length = this.data.length;
    while (true) {
      const leftChild = index * 2 + 1;
      const rightChild = index * 2 + 2;
      let smallest = index;
      if (leftChild < length && this.data[leftChild].distance < this.data[smallest].distance) {
        smallest = leftChild;
      }
      if (rightChild < length && this.data[rightChild].distance < this.data[smallest].distance) {
        smallest = rightChild;
      }
      if (smallest === index) {
        break;
      }
      this.swap(index, smallest);
      index = smallest;
    }
  }

  swap(leftIndex, rightIndex) {
    const temp = this.data[leftIndex];
    this.data[leftIndex] = this.data[rightIndex];
    this.data[rightIndex] = temp;
  }
}

function countPaths(nodeCount, roads) {
  const graph = Array.from({ length: nodeCount }, () => []);
  for (const row of roads) {
    const [left, right, travel] = row;
    graph[left].push({ target: right, time: travel });
    graph[right].push({ target: left, time: travel });
  }
  const distances = new Array(nodeCount).fill(Number.POSITIVE_INFINITY);
  const ways = new Array(nodeCount).fill(0);
  distances[0] = 0;
  ways[0] = 1;
  const heap = new MinHeap();
  heap.push({ node: 0, distance: 0 });

  while (heap.size() > 0) {
    const current = heap.pop();
    if (current.distance > distances[current.node]) {
      continue;
    }
    for (const neighbor of graph[current.node]) {
      const nextDistance = current.distance + neighbor.time;
      if (nextDistance < distances[neighbor.target]) {
        distances[neighbor.target] = nextDistance;
        ways[neighbor.target] = ways[current.node];
        heap.push({ node: neighbor.target, distance: nextDistance });
      } else if (nextDistance === distances[neighbor.target]) {
        ways[neighbor.target] = (ways[neighbor.target] + ways[current.node]) % MODULO;
      }
    }
  }
  return ways[nodeCount - 1];
}