Counting Shortest Paths in Z-Kingdom

Z-Kingdom boasts a comprehensive network of modern roads. During its Independence Celebration, as more tourists pour in from neighboring countries, criminal activities have also begun to emerge quietly. The Special Task Support Unit at the police headquarters has received an urgent request to investigate criminals disguised as tourists. Their investigation led them to a map of Z-Kingdom which records the length of every road in the kingdom.

Since criminals always choose the shortest path to minimize the risk of getting caught, the police now want to know: between any two locations, how many routes could the criminals possibly take? In other words, given an undirected weighted graph that represents the road network, for each query you are to compute the number of distinct shortest paths between two specified nodes.

Input Format:

• The first line contains two integers n and m where n is the number of locations and m is the number of roads.
• The next m lines each contain three integers u, v, and w, representing a bidirectional road between location u and location v with length w.
• The next line contains a single integer q, the number of queries.
• Each of the next q lines contains two integers s and t, representing a query to determine the number of shortest paths between locations s and t.

Output Format:

• For each query, output a single integer indicating the number of distinct shortest paths between the two given locations.

Note: It is guaranteed that the roads define a connected graph and that all roads are bidirectional. Two paths are considered distinct if their sequence of nodes differ, even if the total lengths are equal.

The standard approach uses Dijkstra's algorithm modified to count paths. Recall that if the distance from s to u is dist(u) and the number of ways to reach u is ways(u), then for every edge \( (u, v) \) with weight \( w \), if \( dist(u) + w < dist(v) \) then:

\[ \begin{aligned} dist(v) & = dist(u) + w,\\ ways(v) & = ways(u), \end{aligned} \]

and if \( dist(u) + w = dist(v) \) then you add \( ways(u) \) to \( ways(v) \).

inputFormat

The input begins with two integers n and m (1 ≤ n, m ≤ 10⁵), followed by m lines each containing three integers u, v, and w (1 ≤ u, v ≤ n, 1 ≤ w ≤ 10⁶), describing a bidirectional road. Then follows an integer q (1 ≤ q ≤ 10⁵), the number of queries. Each of the next q lines contains two integers s and t (1 ≤ s, t ≤ n), representing a query to count the number of shortest paths from location s to location t.

outputFormat

For each query, print a single integer on a new line—the number of distinct shortest paths between the specified locations.

sample

4 4
1 2 3
2 3 3
1 3 6
3 4 2
2
1 3
2 4

2
1

</p>