DeliveryBoyz Submit solution All submissions Best submissions Points:15 (partial) Time limit:2.0s Memory limit:12M Author: ritwik Allowed languages C++, Java, Python Suppose you work for a delivery service company that needs to optimize its routing system for delivering packages. The company operates in a city with various locations, and you are tasked with finding the shortest and most efficient paths between different pickup and delivery points. You have access to a map of the city, represented as a weighted graph, where each location is a node, and the edges represent the roads or connections between locations. The weights on the edges represent the distances or travel times between locations.

TASK

Your goal is to develop a program that, given a pickup location and a delivery location, finds the shortest path between them, taking into account the distances and the potential multiple paths available. Create a function that takes the pickup and delivery locations as input and returns the optimal paths along with the total distance.

Input Format:

Copy The first line is the number of cities The next few lines are the cities and distance in the form of an adjacency matrix The next line is the start city The final line is the destination city Output format:

Copy The first line is the optimal path (you may directly print it as a list) The second line is the distance between the 2 points. Sample Input:

Copy 6 0 5 3 0 0 0 5 0 2 0 0 0 3 2 0 8 0 0 0 0 8 0 6 0 0 0 0 6 0 4 0 0 0 0 4 0 0 4 Sample Output:

Copy Optimal path: [0, 2, 3, 4] Total distance: 17