Skip to main content

Flipkart

Flipkart OA 2023 - Shortest Distance Between Two Cities


A taxi company is upgrading its application so that the taxi driver will be shown the shortest distance between two cities in a particular trip. There are N cities, and each city has been identified by a unique Integer from 1 to N. Each city is connected with any other city directly via two routes either using national highways or state highways and both the routes are bidirectional. Also, the taxi company has a policy that on a particular trip the driver can use at most only 1 national highway.

The company's development team wants to build a new algorithm to calculate the shortest distance between the first and second city as per the above-mentioned statements. This new algorivim is designed in such a way that it takes the total number of cities,route Information, and IDs of two cities as input and based on this provided information the algorithm will calculate the shortest distance between the two given cities. The route information which will be provided to the algorithm is in the form of a list consisting of four Integral numbers representing the details of the distance between the two cities

Write an algorithm for the application to find the shortest distance between the first and second city.

Input Format:

  • The first line consists of two space-separated integers: totalCities and routeInformation, representing the total number of cities N and the number of direct routes M between the cities.
  • The next M lines each consist of four space-separated integers: cityA, cityB, stateDistance, nationalDistance, representing:
    • cityA: The first city in the route.
    • cityB: The second city in the route.
    • stateDistance: Distance between the cities via the state highway.
    • nationalDistance: Distance between the cities via the national highway.
  • The second last line consists of an integer, firstCity, representing the starting city for the trip.
  • The last line consists of an integer, secondCity, representing the destination city for the trip.

Output Format:

  • Print an integer representing the shortest distance between the first and second city, considering the restriction of using at most one national highway.
  • If the starting city and destination city are the same, print -1.
  • If no path exists between the two cities, print 0.

Note:

  • If both firstCity and secondCity are the same, print -1.
  • If there is no direct route between two connected cities (either via state or national highway), that respective distance will be marked as 0.

Example:

Input:

4 4
1 4 2 3
1 3 5 1
4 3 10 11
3 2 8 1
4
2

Output:

8

Explanation:

There are multiple paths from city 4 to city 2:

  1. Path 1: 4 → 3 → 2
    Distance = 10 (State) + 8 (State) = 18
    Distance = 11 (National) + 8 (State) = 19
    Distance = 10 (State) + 1 (National) = 11
  2. Path 2: 4 → 1 → 3 → 2
    Distance = 2 (State) + 5 (State) + 8 (State) = 15
    Distance = 2 (State) + 1 (National) + 8 (State) = 11

The shortest valid path is 8 via 4 → 1 → 3 → 2. Therefore, the output is 8.