PreviousNext
Coding/Graphs and trees

Count shortest paths

Write codeHard35 minGoogle style

Your task

Given n nodes (0..n-1) and a list of bidirectional roads [u, v, time] with positive integer travel times, count the number of distinct shortest paths (by total time) from node 0 to node n-1. Return the count modulo 1_000_000_007. If node n-1 is unreachable, return 0. The path from 0 to 0 (when n == 1) counts as 1.

Examples

count_shortest_paths(n: int, roads: list[list[int]]) -> int
Example 1
Inputcount_shortest_paths(4, [[0, 1, 1], [0, 2, 1], [1, 3, 1], [2, 3, 1]])
Output2