Skip to main content

Flipkart

Flipkart OA-7 2023

Problem Description

A taxi company is enhancing its app to help drivers find the shortest route between two cities on any given trip. There are N cities, each represented by a unique integer from 1 to N. Every city is directly connected to any other city through two possible routes: one using national highways and the other using state highways. Both routes are bidirectional.

Additionally, the company has a policy that limits each trip to at most one national highway route.

The development team aims to create an algorithm that calculates the shortest distance between two cities based on these constraints. This algorithm will take as input the total number of cities, route information, and the IDs of two cities. Using this data, the algorithm will compute the shortest path between the specified cities.

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.