Number of Ways to Arrive at Destination
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Number of Shortest Paths in a Weighted Undirected Graph (from node 0 to n-1), Dijkstra's Algorithm, Graph, Adjacency List, Priority Queue, Time Complexity, Space Complexity, Modular Arithmetic, Shortest Path, Weighted Graph, Graph Traversal, Distance Calculation, graph representation, priority queue, dynamic programming, mathematical operations, dijkstra's algorithm, shortest path algorithms, time complexity analysis, Shortest Path Utilities.
You are in a city that consists of n intersections numbered from 0 to n 1 with bi directional roads between some intersections. You can reach any intersection from any other intersection, and there is at most one road between any two intersections. You are given an integer n and a 2D integer array roads where roads[i] = [u i, v i, time i] means that there is a road between intersections u i and v i that takes time i minutes to travel. You want to know in how many ways you can travel from intersection 0 to intersection n 1 in the shortest amount of time. Return the number of ways you can arrive at your destination in the shortest amount of time. Since the answer may be large, return it modulo 10^9 + 7. Example 1: Input: n=7, m=10 edges= [[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 four ways to get there in 7 minutes (which is the shortest calculated time) are: 0 6 0 4 6 0 1 2 5 6 0 1 3 5 6 Example 2: Input: n=6, m=8 edges= [[0,5,8],[0,2,2],[0,1,1],[1,3,3],[1,2,3],[2,5,6],[3,4,2],[4,5,2]] Output: 3 Explanation: The three ways to get there in 8 minutes (which is the shortest calculated time) are: 0 5 0 2 5 0 1 3 4 5