Last Updated: 18 Feb, 2021
Minimum Travel Time
Hard
Asked in company
Mr. X is planning to visit Ninja Land. Ninja Land has 'N' cities numbered from 1 to 'N' and 'M' bidirectional roads. Each road connects two of the 'N' cities, and no two cities have multiple roads between them. Mr. X wants to visit all the 'M' roads and 'N' cities of Ninja land. To do so, he can arbitrarily select any city as the starting city, travel through all the roads, and should end his journey in the same city which he selected as the starting city.
Given the description of each of the 'M' roads i.e, the two 2 cities that the road connects, and the time it takes to travel between the two cities. Your task is to find the minimum time that Mr. X will take to visit all the roads satisfying the above conditions.
If there is no possible way to travel all the roads, then return -1.
Input Format :
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the number of cities and the number of bidirectional roads respectively.
The next 'M' lines of each test case contain the description of the 'M' roads.
The 'i'th' line contains three space-separated integers 'City1', 'City2', and 'Time'. 'City1' and 'City2' denote the two cities that are connected by the 'i'th' road, and 'time' denotes the time it takes to travel between the two cities using this road.
Output Format :
The only line of output of each test case should contain the minimum time that Mr. X will take to visit all the roads satisfying the above conditions. If there is no way to visit all the roads, then print -1.
Print the output of each test case in a new line.
Note :
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10
0 <= M <= (N*(N-1))/2
1 <= City1, City2 <= N
1 <= Time <= 10^6
Any two cities are directly connected by at most one road.
Where 'T' denotes the number of test cases, 'N' denotes the number of cities, 'M' denotes the number of roads, 'City1' and 'City2' denotes the two cities that are connected by the 'i'th' road, and 'Time' denotes the time it takes to travel between the two cities.
Time Limit: 1 sec
Approaches
We will be dividing our solution into four parts for better understanding.
1. Remodeling the problem to a Graph Problem
It is easy to see that the problem can be converted to a Graph Problem. We can build an undirected weighted graph using each of the N cities as Nodes, use the roads as the edges connecting them, and the time it takes to travel between them as the weight of the edge. Now the modified problem becomes to find the smallest weight cycle in a graph such that it covers all the edges.
2. Finding the condition for impossible travel
To check whether, it is possible to travel between all the edges of the graph, we just need to ensure that the Graph is a Connected Graph. This is a trivial graph problem which can be done with the help of Depth First Search (DFS) or Breadth First Search (BFS). If the graph is not connected, then we will return -1 as it will be impossible to travel between all the nodes. Otherwise, we will move to the next step i.e, to find the minimum travel time.
3. Checking if an Eulerian Circuit exist
As we need to travel all the edges exactly once. Ideally, we would like to travel each of the edges exactly once so that the total travel time is minimized. But there can be cases when it is impossible to have a cycle that travels through each edge exactly once. Checking the condition is the same as checking whether an Euler Circuit exists for the graph. This can be done by finding the degree of each of the nodes. If each of the nodes has an even degree, then we will be able to travel through each edge exactly once. In case an Euler Circuit exists, we will return the sum of all the edge weights as the minimum travel time as we are traveling each edge exactly once.
4. Handling the case when the Eulerian circuit does not exist.
If we reach here, this means that at least one node of the graph has an odd degree. By handshaking lemma, we know that the number of nodes having an odd degree in a graph will always be even. We also know that in a cycle, each node is traversed an even number of times. This means, the best case scenario is to visit all the roads of the graph once, and then visit the nodes having an odd degree once, so that the no. of times we visit that node also become even. As we concluded that all the nodes having an odd degree need to be visited an extra time, and there are an even no. of such nodes. This means we can make pairs of all the routes that we will need to cover an extra time. So, we will need to group all the nodes having an odd degree into pairs and generate all such pairs, and take one such pair that produces the minimum travel time.
Let's say for a graph, the nodes W, X, Y, Z have an odd degree. Let shortestDistance[a][b] denotes the shortest distance between Nodes a and b.
All the possible groupings for the above graph will be:
- (W,X), (Y,Z) => Extra travel time = shortestDistance[W][X] + shortestDistance[Y][Z].
- (W,Z), (X,Y) => Extra travel time = shortestDistance[W][Z] + shortestDistance[X][Y].
- (W,Y), (X,Z) => Extra travel time = shortestDistance[W][Y] + shortestDistance[X][Z].
Our extra travel time will be the minimum extra travel time among all such
groupings.
First of all, we will generate the shortest distance between all the pairs of nodes. This can be done with the help of the Floyd-Warshall Algorithm. Let dist[i][j] denote the shortest distance between Node i and Node j. To generate all the pairings, we can use the below recursive algorithm.
Steps :
- The recursive algorithm takes the array of unused nodes unUsed in the current pairing as its parameters.
- Let minTravelTime be the minimum travel time it takes to travel all the unused nodes. Initialize it as INT_MAX.
- If the number of nodes in set S is two, then return dist[unUsed[0]][unUsed[1]] as the minTravelTime. This covers the base case of the recursive function.
- Remove the last element from the array, and store it as city1.
- Iterate through the remaining elements of the array
- Make a temporary array temp equal to the array unUsed.
- Remove the current element from the array temp, and store it as City2
- Call the recursive function for the array temp. Let's currentTravelTime be its returned value.
- Add dist[City1][City2] to currentTravelTime.
- Set minTravelTime time as the minimum value among minTravelTime and currentTravelTime.
- Return the minTravelTime variable.
Now, we need to call the recursive function for all the nodes having an odd degree, and our answer will be the sum of all edge weights and the minTravelTime returned by the Recursive function.