PROBLEM LINK:
Author: Akshat Jain
Tester: Ankit Kathuria
Editorialist: Akshat Jain
DIFFICULTY:
MEDIUM
PREREQUISITES:
Interest in Coding, All Pair Shortest Path.
PROBLEM:
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.
QUICK EXPLANATION:
Here shortest paths among all pairs needs to be calculated and then the maximum out of all those paths is to be displayed.
EXPLANATION:
• 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.