Home Roadmap Courses Problems Dashboard Pricing

Home Roadmap Courses Problems Dashboard Pricing

Loading editor…

Problem 252

Number of Ways to Arrive at Destination

MediumAdvanced Graphs

An undirected weighted graph on n nodes (0 .. n-1). Return the number of shortest paths from 0 to n-1, modulo 1_000_000_007.

Examples

Example 1

Input: [7,[[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

Example 2

Input: [2,[[1,0,10]]]

Output: 1

Constraints

Inputs fit in standard 32-bit integers unless noted.

Target ComplexityNot required

O(V + E) Time · O(V) Space

Companies (6)

AmazonGoogleMetaMicrosoftAppleBloomberg

Node 22.08.0

Loading editor…

Test casesRun to compare output

Input[7,[[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]]]

Expected4

Output—