### 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.