NINJA’S TRIP

Moderate
0/80
Average time to solve is 20m
0 upvote
Asked in company
OYO

Problem statement

Ninja is in a very tense situation as he goes on a trip of mountains but in between his trip, he comes to know that there are various paths between mountains and each mountain has its own limit of weight. Now he starts looking at the map of the city to look for the desired places. This map is in the form of undirected weighted graphs where the edge weight represents the weight mountains can hold between two paths.

Now ninja has some places in mind where he wants to go but with the limit on weight. So help our ninja in checking whether he can go to that place or not.

Your task is to give the answer to ninja queries where he gives you ‘2’ points representing his current location and ending location. You have to return ‘True’ if it is possible to go from that location within the required limit and return ‘False’if it is not possible to go.

Example:

Example

Suppose our query array is [ [ 0, 1, 2 ], [ 0, 2, 5 ] ] so we return False for the first query as there is no edge with a distance less than ‘2’ from ‘0’ to ‘1’.
For the second query, we return ‘True’ as we can indirectly i.e from ‘0’ to ‘1’ which has the weight ‘2’ less than ‘5’ and then ‘1’ to ‘2’ which has the weight ‘4’ less than ‘5’.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains a ‘T’ number of test cases.

The first line of each test case contains a number ‘N’ and ‘M’ representing the number of vertices and rows in array ‘EDGELIST’ respectively. Then, ‘M’ lines follow.

Each line contains ‘3’ space-separated integers denoting the row values where the first value is the starting point, the second value is the ending point and the third value is the weight of the edge.

After ‘M’ lines contain an integer value ‘Q’ denoting the number of queries then ‘Q lines follow

Each line contains ‘3’ space-separated integers denoting the row values where the first value is the starting point, the second value is the ending point and the third value is the weight of the edge.

Output Format:

For each test case, print a single line containing the answer for each query, denoted by ‘True’ if it is possible to go else return ‘False’.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
2 <= N <= 1000
2 <= | EDGELIST | , | QUERY | <= 1000
0 <= EDGELIST[i][j], QUERY[i][j] <= N - 1

Where ‘T’ represents the number of test cases, ‘N’ represents the number of vertices and query length represents the size of the ‘QUERY’ array and ‘EDGELIST’ length represents the size of the ‘EDGELIST’ array.

Time Limit: 1 seC.

Sample Input 1:

2
3 4  
0 1 2
1 2 4
2 0 8
1 0 16
2
0 1 2
0 2 5
5 4
0 1 10
1 2 5
2 3 9
3 4 13
2
0 4 14
1 4 13

Sample Output 1:

False True
True False

Explanation of Sample Input 1:

Test Case 1:

The graph according to the edge list given in the test case is:

Example

So our query array is [ [ 0, 1, 2 ], [ 0, 2, 5 ] ] so we return False for the first query as there is no edge with a distance less than ‘2’ from ‘0’ to ‘1’.
For the second query, we return ‘True’ as we can indirectly i.e from ‘0’ to ‘1’ which has the weight ‘2’ less than ‘5’ and then ‘1’ to ‘2’ which has the weight ‘4’ less than ‘5’.

Test Case 2:

The graph according to the edge list given in the test case is:

Example

So our query array is [ [ 0, 4, 14 ], [ 1, 4, 13 ] ] so we return True for the first query as it is clear from the image we can go that place.
For the second query, we return ‘False’ as we cannot go from ‘3’ to ‘4’ as the edge weight is ‘13’ which is not smaller than our given limit.

Sample Input 2:

2
3  4
0 1 8
1 2 6
2 0 10
1 0 12
2
0 1 11
2 0 5
5 4
0 1 10
1 2 5
2 3 9
3 4 15
2
0 4 18
1 4 16

Sample Output 2:

True False
True True
Hint

Can you use dfs for checking each path?

Approaches (2)
Depth First Search

The idea here is to use dfs and for each query, we have to check that from a given node in query is it possible to reach a given other node in the query by using limit on the weight of edges.

  • We create a 2-d array for taking in consideration whether we have visited that node from a particular node or not.
  • Now we start our dfs for each and every query and try to reach the target by calling recursively for the next node and in every recursive call we check if the weight of the edge is greater than the limit we return False.
  • If we reached the target we return True and repeat the above steps for each query.
Time Complexity

O(N ^ 3), where ‘N’ is the number of the vertex.

 

We are traversing paths from each and every node for each query so basically for each query we traverse each and every node from each node making time complexity as O(N ^ 3).

Space Complexity

O(N ^ 2),  where ‘N’ is the number of the vertex.

 

As we are using a visited array for checking whether we visited or not.

Code Solution
(100% EXP penalty)
NINJA’S TRIP
Full screen
Console