A surveyor has marked n intersections at distinct integer points; intersection i is at points[i] = (x, y). Straight roads join some pairs of intersections: each pair (a, b) in roads is a road between intersections a and b that can be driven in both directions, and its length is the Euclidean distance between its two endpoints. Roads meet only at their end intersections (where two roads cross anywhere else, one passes over the other on a bridge).
A route from start to end is a sequence of roads in which each road begins at the intersection where the previous one ended; its length is the sum of the lengths of its roads. Return the number of routes from start to end whose length equals the smallest possible route length.
If start == end, the empty route is the only shortest route, so the answer is 1. If end cannot be reached, return 0.
Examples
Input: points = [(0, 0), (3, 0), (3, 4), (0, 4)],
roads = [(0, 1), (1, 2), (2, 3), (3, 0), (0, 2)], start = 0, end = 2
Output: 1
Explanation: the diagonal road has length 5; going around the rectangle costs 7.
Input: points = [(0, 0), (1, 0), (1, 1), (0, 1)],
roads = [(0, 1), (1, 2), (2, 3), (3, 0)], start = 0, end = 2
Output: 2
Input: points = [(0, 0), (1, 1), (2, 2)], roads = [(0, 1), (1, 2), (0, 2)], start = 0, end = 2
Output: 2
Explanation: the long road and the two short roads have the same total length.
Constraints
1 <= n <= 300,0 <= len(roads) <= 600-2 * 10**7 <= x, y <= 2 * 10**7, and all points are distinct- no road joins an intersection to itself and no two roads join the same pair
0 <= start, end < n
Goals
- Count shortest paths with Dijkstra
- Recognise when floating point cannot decide a comparison
- Compare sums of square roots reliably