#1976

Number of Ways to Arrive at Destination

expert · 1040 · lc medium +32 · verified · 37.3% accepted · 3,853 likes · top 15%

Description

A city has n intersections (labeled 0 to n - 1) connected by bidirectional roads. Every pair of intersections is reachable from every other, and at most one road exists between any two. You are given roads[i] = [ui, vi, timei] indicating a road between ui and vi requiring timei minutes.

Count the distinct routes from intersection 0 to intersection n - 1 that achieve the minimum total travel time. Return the count modulo 10⁹ + 7.

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

Explanation: The shortest amount of time it takes to go from intersection 0 to intersection 6 is 7 minutes.

The four ways to get there in 7 minutes are:

- 0 ➝ 6

- 0 ➝ 4 ➝ 6

- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6

- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6

Example 2:

Input: n = 2, roads = [[1,0,10]]

Output: 1

Explanation: There is only one way to go from intersection 0 to intersection 1, and it takes 10 minutes.

Code

1

2

3

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:

class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int: