CDIT02 - Editorial

PROBLEM LINK:

Practice

Contest

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.

//