Problem of The Day: Number of Ways to Arrive at Destination
Problem Statement
Brute Force [TLE]
class Solution:
def dijkstra(self, graph, start):
heap = [(0, start)]
shortest_time = {node: float('inf') for node in graph}
shortest_time[start] = 0
while heap:
curr_dist, node = heapq.heappop(heap)
if curr_dist > shortest_time[node]:
continue
for nei, w in graph[node]:
dist = curr_dist + w
if dist < shortest_time[nei]:
shortest_time[nei] = dist
heapq.heappush(heap, (dist, nei))
return shortest_time
def backtrack(self, graph, limit_time, node, n, visited, time, nums_way):
if node == n - 1:
if time == limit_time:
nums_way[0] += 1
return
for x in graph[node]:
nei, t = x
if nei not in visited:
visited.add(nei)
self.backtrack(graph, limit_time, nei, n, visited, time + t, nums_way)
visited.remove(nei)
def countPaths(self, n: int, roads: List[List[int]]) -> int:
graph = {i:[] for i in range(n)}
for u, v, time in roads:
graph[u].append([v, time])
graph[v].append([u, time])
shortest_time = self.dijkstra(graph, 0)
limit_time = shortest_time[n - 1]
num_ways = [0]
for i in range(n):
self.backtrack(graph, limit_time, i, n, set(), time, num_ways)
return num_ways[0]
Try to optimize algorithm but still get TLE.
import heapq
from typing import List
class Solution:
def dijkstra(self, graph, start):
heap = [(0, start)]
shortest_time = {node: float('inf') for node in graph}
shortest_time[start] = 0
while heap:
curr_dist, node = heapq.heappop(heap)
if curr_dist > shortest_time[node]:
continue
for nei, w in graph[node]:
new_dist = curr_dist + w
if new_dist < shortest_time[nei]:
shortest_time[nei] = new_dist
heapq.heappush(heap, (new_dist, nei))
return shortest_time
def backtrack(self, graph, limit_time, node, n, visited, time, num_ways, shortest_time):
if time > limit_time: # Prune unnecessary paths
return
if node == n - 1:
if time == limit_time:
num_ways[0] += 1
return
for nei, t in graph[node]:
if nei not in visited and time + t <= shortest_time[nei]: # Ensure we're following the shortest path
visited.add(nei)
self.backtrack(graph, limit_time, nei, n, visited, time + t, num_ways, shortest_time)
visited.remove(nei)
def countPaths(self, n: int, roads: List[List[int]]) -> int:
graph = {i: [] for i in range(n)}
for u, v, time in roads:
graph[u].append((v, time))
graph[v].append((u, time))
shortest_time = self.dijkstra(graph, 0)
limit_time = shortest_time[n - 1]
num_ways = [0]
self.backtrack(graph, limit_time, 0, n, set([0]), 0, num_ways, shortest_time) # Start from node 0
return num_ways[0]
Editorial
Approach 1: Dijkstra’s Algorithm
class Solution:
def countPaths(self, n: int, roads: list[list[int]]) -> int:
MOD = 1_000_000_007
# Build adjacency list
graph = [[] for _ in range(n)]
for start_node, end_node, travel_time in roads:
graph[start_node].append((end_node, travel_time))
graph[end_node].append((start_node, travel_time))
# Min-Heap (priority queue) for Dijkstra
min_heap = [(0, 0)] # (time, node)
# Store shortest time to each node
shortest_time = [float("inf")] * n
# Number of ways to reach each node in shortest time
path_count = [0] * n
shortest_time[0] = 0 # Distance to source is 0
path_count[0] = 1 # 1 way to reach node 0
while min_heap:
curr_time, curr_node = heapq.heappop(min_heap)
# Skip outdated distances
if curr_time > shortest_time[curr_node]:
continue
for neighbor_node, road_time in graph[curr_node]:
# Found a new shortest path → Update shortest time and reset path count
if curr_time + road_time < shortest_time[neighbor_node]:
shortest_time[neighbor_node] = curr_time + road_time
path_count[neighbor_node] = path_count[curr_node]
heapq.heappush(
min_heap, (shortest_time[neighbor_node], neighbor_node)
)
# Found another way with the same shortest time → Add to path count
elif curr_time + road_time == shortest_time[neighbor_node]:
path_count[neighbor_node] = (
path_count[neighbor_node] + path_count[curr_node]
) % MOD
return path_count[n - 1]
Approach 2: Floyd-Warshall algorithm
class Solution:
MOD = 1_000_000_007
def countPaths(self, n: int, roads: list[list[int]]) -> int:
# dp[src][dest][0] stores the minimum time between src and dest
# dp[src][dest][1] stores the number of ways to reach dest from src
# with the minimum time
dp = [[[0, 0] for _ in range(n)] for _ in range(n)]
# Initialize the dp table
for src in range(n):
for dest in range(n):
if src != dest:
# Set a large initial time
dp[src][dest][0] = int(1e12)
# No paths yet
dp[src][dest][1] = 0
else:
# Distance from a node to itself is 0
dp[src][dest][0] = 0
# Only one trivial way (staying at the node)
dp[src][dest][1] = 1
# Initialize direct roads from the input
for start_node, end_node, travel_time in roads:
dp[start_node][end_node][0] = travel_time
dp[end_node][start_node][0] = travel_time
# There is one direct path
dp[start_node][end_node][1] = 1
# Since the roads are bidirectional
dp[end_node][start_node][1] = 1
# Apply the Floyd-Warshall algorithm to compute shortest paths
# Intermediate node
for mid in range(n):
# Starting node
for src in range(n):
# Destination node
for dest in range(n):
# Avoid self-loops
if src != mid and dest != mid:
new_time = dp[src][mid][0] + dp[mid][dest][0]
if new_time < dp[src][dest][0]:
# Found a shorter path
dp[src][dest][0] = new_time
dp[src][dest][1] = (
dp[src][mid][1] * dp[mid][dest][1]
) % self.MOD
elif new_time == dp[src][dest][0]:
# Another way to achieve the same shortest time
dp[src][dest][1] = (
dp[src][dest][1]
+ dp[src][mid][1] * dp[mid][dest][1]
) % self.MOD
# Return the number of shortest paths from node (n-1) to node 0
return dp[n - 1][0][1]
