A delivery app wants to show how many different routes tie for the fastest time from the warehouse to a customer. Places are numbered 0 to n - 1, with the warehouse at 0 and the customer at n - 1. Each roads[i] = [a, b, minutes] is a two-way road.
Write countFastest(n, roads) that returns the number of different routes from 0 to n - 1 whose total time equals the fastest possible time. The count can be large, so return it modulo 1000000007. The customer is always reachable.
Input: n = 4, roads = [[0,1,1],[0,2,1],[1,3,1],[2,3,1]] Output: 2
Both 0 → 1 → 3 and 0 → 2 → 3 take 2 minutes.
Input: n = 3, roads = [[0,1,1],[1,2,1],[0,2,3]] Output: 1
0 → 1 → 2 takes 2 minutes, beating the direct road's 3.
1 <= n <= 200n - 1 <= roads.length <= n * (n - 1) / 21 <= minutes <= 10^9Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.
Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).
I'm here to help with #462 Count the Fastest Routes. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.