Counting Shortcuts (Codeforces 1650G)
Tags: Others, shortest paths

Given an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. The graph contains no loops (edges from a vertex to itself) and multiple edges (i.e. no more than one edge between each pair of vertices). The vertices of the graph are numbered from $$$1$$$ to $$$n$$$. Find the number of paths from a vertex $$$s$$$ to $$$t$$$ whose length differs from the shortest path from $$$s$$$ to $$$t$$$ by no more than $$$1$$$. It is necessary to consider all suitable paths, even if they pass through the same vertex or edge more than once (i.e. they are not simple).  Graph consisting of $$$6$$$ of vertices and $$$8$$$ of edges For example, let $$$n = 6$$$, $$$m = 8$$$, $$$s = 6$$$ and $$$t = 1$$$, and let the graph look like the figure above. Then the length of the shortest path from $$$s$$$ to $$$t$$$ is $$$1$$$. Consider all paths whose length is at most $$$1 + 1 = 2$$$.   $$$6 \rightarrow 1$$$. The length of the path is $$$1$$$.  $$$6 \rightarrow 4 \rightarrow 1$$$. Path length is $$$2$$$.  $$$6 \rightarrow 2 \rightarrow 1$$$. Path length is $$$2$$$.  $$$6 \rightarrow 5 \rightarrow 1$$$. Path length is $$$2$$$. There is a total of $$$4$$$ of matching paths.

Input: The first line of test contains the number $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.Before each test case, there is a blank line. The first line of test case contains two numbers $$$n, m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$) —the number of vertices and edges in the graph. The second line contains two numbers $$$s$$$ and $$$t$$$ ($$$1 \le s, t \le n$$$, $$$s \neq t$$$) —the numbers of the start and end vertices of the path.The following $$$m$$$ lines contain descriptions of edges: the $$$i$$$th line contains two integers $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$) — the numbers of vertices that connect the $$$i$$$th edge. It is guaranteed that the graph is connected and does not contain loops and multiple edges.It is guaranteed that the sum of values $$$n$$$ on all test cases of input data does not exceed $$$2 \cdot 10^5$$$. Similarly, it is guaranteed that the sum of values $$$m$$$ on all test cases of input data does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single number — the number of paths from $$$s$$$ to $$$t$$$ such that their length differs from the length of the shortest path by no more than $$$1$$$.Since this number may be too large, output it modulo $$$10^9 + 7$$$.


Sample Inputs:
4
4 4
1 4
1 2
3 4
2 3
2 4
6 8
6 1
1 4
1 6
1 5
1 2
5 6
4 6
6 3
2 6
5 6
1 3
3 5
5 4
3 1
4 2
2 1
1 4
8 18
5 1
2 1
3 1
4 2
5 2
6 5
7 3
8 4
6 4
8 7
1 4
4 7
1 6
6 7
3 8
8 5
4 5
4 3
8 2

Sample Outputs:
2
4
1
11

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
    I()
    (n, m) = I()
    (s, t) = I()
    M = 10 ** 9 + 7
    s -= 1
    t -= 1
    g = [[] for i in range(n)]
    for i in range(m):
        (u, v) = I()
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    distances = [M] * n
    distances[s] = 0
    i = 0
    paths = {s: 1}
    tot = 0
    while i <= distances[t]:
        i += 1
        newpaths = {}
        for v in paths:
            for w in g[v]:
                if distances[w] >= i - 1:
                    distances[w] = min(distances[w], i)
                    if w in newpaths:
                        newpaths[w] = (newpaths[w] + paths[v]) % M
                    else:
                        newpaths[w] = paths[v]
        paths = newpaths
        if t in paths:
            tot += paths[t]
    print(tot % M)

Solution (Python):
import sys
I = lambda : [*map(int, sys.stdin.readline().split())]
(t,) = I()
for _ in range(t):
    I()
    (n, m) = I()
    (s, t) = I()
    M = 10 ** 9 + 7
    s -= 1
    t -= 1
    g = [[] for i in range(n)]
    for i in range(m):
        (u, v) = I()
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    distances = [M] * n
    distances[s] = 0
    i = 0
    paths = {s: 1}
    tot = 0
    while i <= distances[t]:
        i += 1
        newpaths = {}
        for v in paths:
            for w in g[v]:
                if distances[w] >= i - 1:
                    distances[w] = min(distances[w], i)
                    if w in newpaths:
                        newpaths[w] = (newpaths[w] + paths[v]) % M
                    else:
                        newpaths[w] = paths[v]
        paths = newpaths
        if t in paths:
            tot += paths[t]
    print(tot % M)

Solution (Python):
from collections import deque
mod = 10 ** 9 + 7

def add(a, b):
    return (a % mod + b % mod) % mod

def answer():
    whichlevel = [-1 for i in range(n + 1)]
    whichlevel[s] = 0
    q = deque([s])
    while len(q):
        p = q.popleft()
        for i in adj[p]:
            if whichlevel[i] != -1:
                continue
            whichlevel[i] = whichlevel[p] + 1
            q.append(i)
    dp = [[0, 0] for i in range(n + 1)]
    dp[s][0] = 1
    v = [[False, False] for i in range(n + 1)]
    q = deque([[s, 0]])
    while len(q):
        (p, lvl) = q.popleft()
        parentlvldiff = lvl - whichlevel[p]
        if v[p][parentlvldiff]:
            continue
        v[p][parentlvldiff] = True
        for i in adj[p]:
            if lvl + 1 - whichlevel[i] > 1:
                continue
            childlvldiff = lvl + 1 - whichlevel[i]
            dp[i][childlvldiff] = add(dp[i][childlvldiff], dp[p][parentlvldiff])
            q.append([i, lvl + 1])
    ans = add(dp[t][0], dp[t][1])
    return ans
for T in range(int(input())):
    input().strip()
    (n, m) = map(int, input().split())
    (s, t) = map(int, input().split())
    adj = [[] for i in range(n + 1)]
    for i in range(m):
        (u, v) = map(int, input().split())
        adj[u].append(v)
        adj[v].append(u)
    print(answer())