Count the Number of Shortest Paths Between Two Nodes in an Undirected Graph

Problem: Count the Number of Shortest Paths Between Two Nodes in an Undirected Graph You are given a weighted undirected graph G = (V, E) where each edge e=(u,v,w) has a non-negative integer weight w. Given a source node s and a target node t, compute the number of shortest paths from s to t (two paths are different if their vertex/edge sequences differ). If t is unreachable from s, return 0. You only need to output the count, not the paths themselves. Input format (stdin) n m u1 v1 w1 u2 v2 w2 ... um vm wm s t n: number of nodes labeled 0..n-1 m: number of edges Next m lines: undirected edges Last line: s t Output format (stdout) count Constraints 1 <= n <= 2e5 0 <= m <= 2e5 0 <= wi <= 1e9 The graph may be disconnected and may contain multi-edges. Example 1 Input: 5 6 0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 1 2 2 0 4 Output: 2 Explanation: shortest distance from 0 to 4 is 3, with two shortest paths: 0-1-3-4 and 0-2-3-4. Example 2 Input: 3 1 0 1 5 0 2 Output: 0 Example Input 5 6 0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 1 2 2 0 4 Output 2