Author: Akshat Jain
Tester: Ankit Kathuria
Editorialist: Akshat Jain
Interest in Coding, All Pair Shortest Path.
Maximum fare is to be calculated to go from any one friend’s station to another friend’s station while travelling through the shortest path possible between them.
Here shortest paths among all pairs needs to be calculated and then the maximum out of all those paths is to be displayed.
• The first input is the number of test cases followed by number of nodes and number of edges.
• Each edge contains the start, end and edge length. This data can be very well stored in adjacency matrix form.
• Now all pair shortest path algorithm i.e. Warshall’s algorithm is applied to obtain a matrix containing desired shortest paths.
• Finally calculate the maximum value out of that array, multiply it with 5 and display the result.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.