Problem Description

You have an undirected weighted connected graph with n nodes labeled from 1 to n. The graph is defined by an array edges where each edges[i] = [ui, vi, weighti] represents an edge between nodes ui and vi with weight weighti.

A path from node start to node end is a sequence of nodes [z0, z1, z2, ..., zk] where:

• z0 = start and zk = end
• There exists an edge between consecutive nodes zi and zi+1 for all 0 <= i <= k-1

The distance of a path is the sum of all edge weights along that path.

Let distanceToLastNode(x) represent the shortest distance from node x to node n.

A restricted path is a path that satisfies an additional constraint: for every step in the path, you must move to a node that is strictly closer to node n. Formally, distanceToLastNode(zi) > distanceToLastNode(zi+1) for all 0 <= i <= k-1.

Your task is to count the number of restricted paths from node 1 to node n. Since this number can be very large, return the result modulo 10^9 + 7.

In essence, you need to find all possible paths from node 1 to node n where each step moves to a node with a smaller shortest distance to node n than the current node.

Intuition

The key insight is that we need to find paths where each step moves to a node that is strictly closer to the destination (node n). This suggests we should first know the shortest distance from every node to node n.

Think of it like walking downhill - if we know the "elevation" (shortest distance to node n) of every node, then a restricted path is like always stepping down to lower elevations until we reach the bottom (node n).

This naturally breaks down into two main tasks:

1. Find shortest distances: We need to calculate distanceToLastNode(x) for every node x. Since we want distances from all nodes to node n, we can run Dijkstra's algorithm starting from node n itself. This gives us the shortest distance from node n to every other node, which is exactly what we need.

2. Count valid paths: Once we know the distances, we need to count paths from node 1 to node n where each step goes to a node with a smaller distance value. This is a classic dynamic programming problem - the number of restricted paths from any node i equals the sum of restricted paths from all its neighbors j where dist[i] > dist[j].

The beauty of this approach is that the restriction distanceToLastNode(zi) > distanceToLastNode(zi+1) ensures we never revisit a node (no cycles), making the counting problem tractable with memoization. We can use DFS with memoization starting from node 1, and at each node, we only explore neighbors that have smaller distances to node n.

The modulo operation 10^9 + 7 is applied during the counting phase to prevent integer overflow since the number of paths can be exponentially large.

Learn more about Graph, Topological Sort, Dynamic Programming, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The implementation consists of two main phases: computing shortest distances using Dijkstra's algorithm and counting restricted paths using DFS with memoization.

Phase 1: Computing Shortest Distances with Dijkstra's Algorithm

First, we build an adjacency list representation of the graph:

g = defaultdict(list)
for u, v, w in edges:
    g[u].append((v, w))
    g[v].append((u, w))

Then we run Dijkstra's algorithm starting from node n:

q = [(0, n)]  # Priority queue: (distance, node)
dist = [inf] * (n + 1)  # Initialize all distances to infinity
dist[n] = 0  # Distance from n to itself is 0

while q:
    _, u = heappop(q)
    for v, w in g[u]:
        if dist[v] > dist[u] + w:
            dist[v] = dist[u] + w
            heappush(q, (dist[v], v))

The priority queue ensures we always process the node with the smallest distance first. After this phase, dist[i] contains the shortest distance from node i to node n.

Phase 2: Counting Restricted Paths with DFS and Memoization

We use a recursive DFS function with @cache decorator for memoization:

@cache
def dfs(i):
    if i == n:  # Base case: reached destination
        return 1
    ans = 0
    for j, _ in g[i]:  # Check all neighbors
        if dist[i] > dist[j]:  # Only move to nodes closer to n
            ans = (ans + dfs(j)) % mod
    return ans

The function dfs(i) returns the number of restricted paths from node i to node n. The key points are:

1. Base case: If we're at node n, there's exactly one path (the empty path)
2. Recursive case: For each neighbor j of node i, if dist[i] > dist[j] (meaning j is closer to n), we add the number of paths from j to our answer
3. Memoization: The @cache decorator ensures we don't recompute the same subproblem multiple times

Finally, we return dfs(1) to get the number of restricted paths from node 1 to node n.

The time complexity is O(E log V) for Dijkstra's algorithm plus O(V + E) for the DFS traversal, where V is the number of nodes and E is the number of edges. The space complexity is O(V + E) for storing the graph and distance array.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider a graph with 5 nodes and the following edges:

• Edge (1, 2) with weight 1
• Edge (1, 3) with weight 1
• Edge (2, 4) with weight 1
• Edge (3, 4) with weight 2
• Edge (2, 5) with weight 2
• Edge (4, 5) with weight 1

We want to count restricted paths from node 1 to node 5.

Step 1: Run Dijkstra's algorithm from node 5

Starting from node 5, we compute shortest distances:

• Process node 5: dist[5] = 0
• Process neighbors of 5:
  • Node 2: dist[2] = 0 + 2 = 2
  • Node 4: dist[4] = 0 + 1 = 1
• Process node 4 (smallest unprocessed distance):
  • Node 2: dist[2] stays 2 (not improved)
  • Node 3: dist[3] = 1 + 2 = 3
• Process node 2:
  • Node 1: dist[1] = 2 + 1 = 3
  • Node 4: already processed
• Process node 3:
  • Node 1: dist[1] stays 3 (not improved)

Final distances to node 5:

• dist[1] = 3
• dist[2] = 2
• dist[3] = 3
• dist[4] = 1
• dist[5] = 0

Step 2: Count restricted paths using DFS with memoization

Starting from node 1 (dist = 3):

• Check neighbor 2: dist[2] = 2 < 3 ✓ (valid move)
  • From node 2 (dist = 2):
    • Check neighbor 4: dist[4] = 1 < 2 ✓
      • From node 4 (dist = 1):
        • Check neighbor 5: dist[5] = 0 < 1 ✓
          • Node 5 is destination, return 1
        • Total from node 4: 1 path
    • Check neighbor 5: dist[5] = 0 < 2 ✓
      • Node 5 is destination, return 1
    • Total from node 2: 1 + 1 = 2 paths
• Check neighbor 3: dist[3] = 3, not < 3 ✗ (invalid move)
• Total from node 1: 2 paths

The two restricted paths are:

1. 1 → 2 → 4 → 5 (distances: 3 → 2 → 1 → 0)
2. 1 → 2 → 5 (distances: 3 → 2 → 0)

Both paths satisfy the restriction that each step moves to a node strictly closer to node 5. The answer is 2.

Solution Implementation

Time and Space Complexity

Time Complexity: O(E log V + V + E)

Breaking down the time complexity:

• Building the adjacency list from edges takes O(E) where E is the number of edges
• Dijkstra's algorithm to compute shortest distances from node n:
  • Each node can be pushed to the heap at most once: O(V) operations
  • Each edge is relaxed at most once: O(E) operations
  • Each heap operation (push/pop) takes O(log V)
  • Total for Dijkstra's: O((V + E) log V) which simplifies to O(E log V) since typically E ≥ V-1 in connected graphs
• DFS with memoization:
  • Each node is visited at most once due to @cache
  • For each node, we iterate through its neighbors
  • Total: O(V + E) for traversing all nodes and edges once

Overall: O(E log V + V + E) = O(E log V) as the Dijkstra's term dominates

Space Complexity: O(V + E)

Breaking down the space complexity:

• Adjacency list g stores all edges: O(E)
• Distance array dist of size n+1: O(V)
• Priority queue can contain at most V nodes: O(V)
• Cache for DFS memoization stores at most V results: O(V)
• Recursion stack depth in worst case: O(V)

Overall: O(V + E) since we need to store the graph structure and various auxiliary arrays

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Wrong Starting Node for Dijkstra's Algorithm

A critical pitfall is running Dijkstra's algorithm from node 1 instead of node n. Since we need distanceToLastNode(x) (the shortest distance from node x to node n), we must start Dijkstra from node n, not from node 1.

Incorrect approach:

# Wrong: Starting from node 1
distance[1] = 0
priority_queue = [(0, 1)]

Correct approach:

# Correct: Starting from node n
distance[n] = 0
priority_queue = [(0, n)]

2. Not Handling the Priority Queue Optimization

When using Dijkstra's algorithm with a min-heap, the same node might be added to the queue multiple times with different distances. Failing to skip outdated entries can lead to incorrect results or inefficiency.

Missing optimization:

while priority_queue:
    current_dist, current_node = heappop(priority_queue)
    # Missing check - might process same node multiple times
    for neighbor, edge_weight in graph[current_node]:
        # ...

With optimization:

while priority_queue:
    current_dist, current_node = heappop(priority_queue)
  
    # Skip if we've already found a shorter path
    if current_dist > distance[current_node]:
        continue
  
    for neighbor, edge_weight in graph[current_node]:
        # ...

3. Forgetting to Apply Modulo During Accumulation

Since the number of paths can be very large, forgetting to apply modulo during accumulation can cause integer overflow in languages with fixed-size integers, or lead to incorrect results.

Incorrect:

def count_paths(node):
    if node == n:
        return 1
    path_count = 0
    for next_node, _ in graph[node]:
        if distance[node] > distance[next_node]:
            path_count += count_paths(next_node)  # Missing modulo
    return path_count % MOD  # Only applying modulo at the end

Correct:

def count_paths(node):
    if node == n:
        return 1
    path_count = 0
    for next_node, _ in graph[node]:
        if distance[node] > distance[next_node]:
            path_count = (path_count + count_paths(next_node)) % MOD  # Apply modulo during accumulation
    return path_count

4. Confusion About the Direction of Movement

The problem states we need to move to nodes that are "strictly closer to node n". This means distance[current] > distance[next], not the other way around.

Wrong condition:

# Incorrect: This would move away from node n
if distance[node] < distance[next_node]:
    path_count = (path_count + count_paths(next_node)) % MOD

Correct condition:

# Correct: Move to nodes closer to n
if distance[node] > distance[next_node]:
    path_count = (path_count + count_paths(next_node)) % MOD

5. Not Using Memoization

Without memoization, the DFS solution would have exponential time complexity because the same subproblems would be computed multiple times. This would cause Time Limit Exceeded for larger inputs.

Without memoization (inefficient):

def count_paths(node):
    if node == n:
        return 1
    # ... rest of the logic

With memoization (efficient):

@cache  # or use a manual memo dictionary
def count_paths(node):
    if node == n:
        return 1
    # ... rest of the logic