Tester: Akshay Venkataramani
Graph, BFS, Shortest Path Algorithms
The question requires a reversal of perspective. Trying to find the shortest distance to the finish line(node N) from each of the starting points(nodes 1 to S) gives a TLE. Instead, we can find the shortest distance from node N to nodes 1 to S.
This can be done using shortest path algorithms like Dijkstra’s or by using a BFS, which is O(N), since the graph is unweighted.
Once the shortest distances to all nodes are found, it is just a matter of finding the count of the maximum distances.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.