Friends Trip

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
2 upvotes
Asked in company
Adobe

Problem statement

‘N’ friends have to go trekking to a location. One of them presents the location map as a list of ‘N’ nodes and ‘M’ weighted directed edges between the nodes, representing the time it takes to go from one location to another. All the friends decide to start from location ‘S’ and meet at location ‘D’. You have to find the minimum time it will take such that one friend in the group will visit one location each and meet at location ‘D’. It takes 1 unit of time to visit a location. If not possible to visit all locations, then return -1.

For example: 
You are given the following graph. S = 1 and D = 3:

WeightedGraph2

Friend 1 will visit location 1 in 1 unit time and then go to location 3 in 6 units of time. The total time is 7.

Friend 2 will go from 1 to 2 in 4 units time, then visited 2 in 1 unit time and go to 3 in 2 units. The total time is 7.

Friend 3 will go from 1 to 3 in 6 units and visit 3 in 1 unit. The total time is 7.

Hence everyone will reach location 3 in a maximum of 7 units of time. Therefore 7 is the answer.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains the single integer ‘T’ representing the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, representing the number of nodes and edges in the graph.

The second line of each test case contains two integers, ‘S’ and ‘D’, representing the starting point and destination.

The next M lines of each test case contain three space-separated integers ‘A’ ‘B’ and ‘W’, representing an edge from the node ‘A’ to the node ‘B’ whose weight is ‘W.’
Output Format: 
For each test case, print a single integer representing the minimum time it will take such that one friend in the group will visit one location each and meet at location ‘D.’

For each test case, print a separate line.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10^5
1 <= A, B <= N
1 <= S, D <= N
1 <= W <= 10^7

Time Limit: 1 sec
Sample Input 1:
2
3 2
1 3
1 2 4
2 3 2
5 5
1 5
1 2 3
2 3 2
2 5 5
3 4 1
3 5 5
Sample Output 1:
7
-1
Explanation:
For the first test case, you are given the following graph, S = 1 and D = 3:

WeightedGraph2

Friend 1 will visit location 1 in 1 unit time and then go to location 3 in 6 units of time. The total time is 7
Friend 2 will go from 1 to 2 in 4 units, then visited 2 in 1 unit and went to 3 in 2 units. The total time is 7
Friend 3 will go from 1 to 3 in 6 units and visit 3 in 1 unit. The total time is 7
Hence everyone will reach location 3 in a maximum of 7 units of time. Therefore 7 is the answer.

For the second test case, you are given the following graph, S = 1 and D = 5:

WeightedGraph

Here it is not possible to visit location 4 and meet at location 5. Hence the answer is  -1.
Sample Input 2:
2
4 4
1 4
1 2 3
2 3 3
3 4 1
4 1 2
3 4
1 3
1 2 1
2 1 2
2 3 1
3 2 1
Sample Output 2:
8
3
Hint

Try to reverse the path.

Approaches (2)
Bellman-Ford

In this approach, we will find the minimum distance between the source and every other node. Then we will reverse all the edges of the graph given and find the shortest distance between the destination and every other node. Then we will add the distances from both source and destination and add 1 to it. Then will be the maximum value of all the distances sum + 1.

 

We will create a function bellmanFord(edges, n, source). The parameter edge is the edge list, n is the number of nodes, and the source is the starting node. This function will return the list of distances of all nodes from the source.

 

Algorithm:

  • The function bellmanFord(edges, n, source): where the parameter edges is the edge list, n is the number of nodes, and the source is the starting node.
    • Create a distances list of length n with all values initialized to the maximum value of the integer.
    • Set the distance of source distances[source] as 0
    • Iterate from 0 to n - 1
      • Iterate edge through the array edges
        • Set currSource as edge[0] - 1
        • Set currDest as edge[1] - 1.
        • Set weight as edge[2].
        • Set distances[currDest] as the minimum of distances[currDest] and the sum of distances[currSource] and weight.
    • After the while loop ends, return the list distances.
  • Create an empty array revEdges
  • Iterate edge through edges
    • Set source, destination, weight as edge[0], edge[1], edge[2], respectively
    • Insert the array [destination, source, weight] into revEdges
  • Set startDistances as belmanFord(s - 1, edges, n)
  • Set endDistances as belmanFord(d - 1, revEdges, n)
  • Set ans as 0
  • Iterate i from 0 to size of startDistances  - 1
    • If startDistances[i] or endDistances[i] equal to maximum value of integer
      • Return -1
    • Set ans as maximum of ans and startDistances[i] +  endDistances[i] + 1
  • Finally, return ans
Time Complexity

O(N*M), Where N and M are the numbers of nodes and edges in the graph.

 

We are doing N iterations, and in each iteration, we are traversing through the edges that take O(M) time. Hence, the overall time complexity becomes O(N*M).

Space Complexity

O(N + M), Where N and M are the numbers of nodes and edges in the graph.

 

We are maintaining a distances array that takes O(N) space. We are also maintaining a reverse edges list which will take O(M) space. Hence the overall space complexity becomes O(N) + O(M) = O(N + M).

Code Solution
(100% EXP penalty)
Friends Trip
Full screen
Console