You are in a city that consists of n intersections numbered from 0 to n - 1 with bi-directional roads between some intersections. The inputs are generated such that you can reach any intersection from any other intersection and that 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
Explaination:
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=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
Explaination:
The three ways to get there in 8 minutes are:
- 0  5
- 0  2  5
- 0  1  3  4  5
 
Constraints:
1 <= n <= 200
n - 1 <= roads.length <= n * (n - 1) / 2
roads[i].length == 3
0 <= u_{i}, v_{i} <= n - 1
1 <= time_{i} <= 10^{9}
u_{i }!= v_{i}
There is at most one road connecting any two intersections.
You can reach any intersection from any other intersection.
Expected Time Complexity: O(M * logN + N)
Expected Space Complexity: O(M+N)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Shortest paths

Starter code: #User function Template for python3



from typing import List

from collections import defaultdict

import sys

class Solution:

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

        #Your code here

Solutions:
from typing import List
from collections import defaultdict
import heapq
import sys

class Solution:

	def countPaths(self, n: int, roads: List[List[int]]) -> int:
		mod = 10 ** 9 + 7
		adj = defaultdict(list)
		for (u, v, w) in roads:
			adj[u].append([v, w])
			adj[v].append([u, w])
		distance = [float('inf')] * n
		ways = [0] * n
		distance[0] = 0
		ways[0] = 1
		q = []
		heapq.heappush(q, [0, 0])
		while len(q) != 0:
			(dist, node) = heapq.heappop(q)
			for i in adj[node]:
				(v, w) = i
				d = dist + w
				if distance[v] > d:
					distance[v] = d
					heapq.heappush(q, [distance[v], v])
					ways[v] = ways[node]
				elif distance[v] == d:
					ways[v] += ways[node] % mod
		return ways[n - 1]


from typing import List
from collections import defaultdict
import sys, heapq

class Solution:

	def countPaths(self, n: int, roads: List[List[int]]) -> int:
		mod = 10 ** 9 + 7
		ways = [0 for i in range(n)]
		ways[0] = 1
		dis = [float('inf') for i in range(n)]
		dis[0] = 0
		dict = defaultdict(list)
		for (src, dst, cost) in roads:
			dict[src].append([dst, cost])
			dict[dst].append([src, cost])
		li = []
		heapq.heappush(li, [0, 0])
		while len(li):
			(time, node) = heapq.heappop(li)
			for (nei, cost) in dict[node]:
				if time + cost < dis[nei]:
					dis[nei] = time + cost
					ways[nei] = ways[node]
					heapq.heappush(li, [time + cost, nei])
				elif time + cost == dis[nei]:
					ways[nei] += ways[node] % mod
		return ways[-1]


from typing import List
from queue import PriorityQueue as pq
from collections import defaultdict as dqs
import sys

class Solution:

	def countPaths(self, n: int, roads: List[List[int]]) -> int:
		dq = dqs(list)
		for i in roads:
			dq[i[0]].append([i[1], i[2]])
			dq[i[1]].append([i[0], i[2]])
		q = pq()
		d = [float('inf')] * n
		ways = [0] * n
		d[0] = 0
		ways[0] = 1
		q.put([0, 0])
		while not q.empty():
			node = q.get()
			dist = node[0]
			curr = node[1]
			for i in dq[curr]:
				des = i[0]
				cost = i[1]
				if d[des] > cost + dist:
					d[des] = cost + dist
					ways[des] = ways[curr]
					q.put([dist + cost, des])
				elif d[des] == cost + dist:
					ways[des] = ways[des] + ways[curr]
		return ways[n - 1]


from typing import List
from collections import defaultdict
import sys
import heapq

class Solution:

	def countPaths(self, n: int, roads: List[List[int]]) -> int:
		adj = defaultdict(list)
		for (node1, node2, cost) in roads:
			adj[node1].append((node2, cost))
			adj[node2].append((node1, cost))
		store = defaultdict(int)
		store[0, 0] = 1
		visited = set()
		heap = [(0, 0)]
		while heap:
			(time, node) = heapq.heappop(heap)
			if node == n - 1:
				return store[time, n - 1] % (10 ** 9 + 7)
			if node in visited:
				continue
			visited.add(node)
			for (target, cost) in adj[node]:
				temp = time + cost
				store[temp, target] += store[time, node]
				heapq.heappush(heap, (temp, target))
		return 0