Last Updated: 14 Oct, 2021
Travel Nodes
Moderate
Asked in company
Ninja is practicing questions on the graph where he came across a question in which he has given an undirected graph with ‘N’ nodes with ‘M’ edges. The nodes are numbered from 1 to ‘N’. Initially, Ninja is present on the 1st node. Each node has a weight associated with it given in array ‘WEIGHT’. Ninja needs to travel all the nodes on the following conditions:
1. Start from node 1 and move to the next unvisited node having the highest weight.
2. If two or more nodes have the same weight, move to the node, which takes less time to move to another node.
3. If there are no adjacent unvisited nodes at a point, then you have to traverse back to the previous node from where you came to the present node for the first time.
4. Repeat the above process till all the nodes are visited.
Ninja is provided with the time between two connected nodes, which denotes the time required to travel between two connected nodes. Ninja's task is to find the time arrival at each node for the first time.
Example:
Let the number of nodes be: 3
Let there be an edge between nodes 1 and 3 and between nodes 1 and 2.
Let the time required to reach from node 1 to 3 be 2 units and node 1 to 2 be 4 units.
Let the weights of each node be: [0, 1, 1]
The graph for above will be:
We start from node 1. Its adjacent nodes are: {2, 3} out of which both nodes have the same weights, but the time needed to reach node 3 is less so we first move to node 3, so the first arrival time at node 3 will be 2 units.
We then move to node 3 whose adjacent nodes are: {1} which is already visited.
We move back to node 1, which takes 2 units of time. 2 + 2 = 4 units.
We then move to node 2 from node 1, which takes 4 + 4 = 8 units.
Hence the answer is [0, 8, 2].
Input Format :
The first line of input contains an integer ‘T’, 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, number of edges, respectively.
Each test case’s next ‘M’ lines contain two single space-separated integers, ‘X', 'Y', and ‘D’, which signifies an edge between ‘X’ and ‘Y’, and the time taken to travel between the two nodes, respectively.
The ‘M’ + 1 line of each test case contains ‘N’ single space-separated integers, representing the weight of each node.
Output Format :
For each test case, print 'N' space-separated integers representing the time arrival at each node for the first time.
Print output of each test case 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 <= 10
1 <= N <= 10^3
N - 1 <= M <= min(N* (N - 1) / 2, 10^3)
1 <= X, Y <= N
1 <= WEIGHT[i] <= 10^9
1 <= D <= 10^6
Time Limit: 1 sec
Approaches
The basic idea is to use a depth-first search to travel the nodes. We travel all the nodes of the adjacent nodes to find the node with maximum weight, and if weight is equal, we check for the least time required to travel between the nodes. We also need to store the time to travel between the current node and the previous node to add when we travel back to any of the nodes.
Here is the algorithm :
- Create a weighted graph (say, ‘GRAPH’) using the ‘EDGES’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
- Push the edges and time in the ‘GRAPH’.
- Create an array (say, ‘VISITED’) which will be used to mark all the visited vertices and initialize it with ‘FALSE’ for every vertex present in the ‘GRAPH’.
- Create a variable (say, ‘D’) to store the time needed to travel from one node to another.
- Create an array (say, ‘RES’) to store the first arrival time of each node.
- Call the ‘DFS’ function, DFS(‘GRAPH’, ‘VISITED’, ‘WEIGHT’, ‘RES’, 0, ‘D’, 0)
- Finally, return ‘RES’.
DFS(‘GRAPH’, ‘VISITED’, ‘WEIGHT’, ‘RES’, U, ‘D’, ‘PRE’) (where ‘U’ is the current node, ‘PRE’ is the time taken to reach the current node from the previous node).
- Mark ‘U’ as visited in the ‘VISITED’ array.
- Set ‘RES[U]’ as ‘D’.
- Iterate over all the adjacent vertices of the ‘U’ (say, iterator ‘i’).
- Create variables (say, ‘WT’, ‘T’, and ‘V’) that store maximum weight, time, and the next node to be taken.
- Iterate all the adjacent vertices of the ‘U’ again (say, iterator ‘j’) to find the node according to the conditions.
- Let the adjacent node be ‘NEXT’ with the weight ‘TEMP’.
- Check if ‘NEXT’ is unvisited.
- Check if ‘WEIGHT[V]’ is greater than ‘WT’, update the ‘WT’, ‘T’, and ‘V’ values.
- Else, check if ‘WEIGHT[V]’ is equal to ‘WT’ and ‘T’ is greater than ‘TEMP’ and update the ‘WT’, ‘T’, and ‘V’ values.
- Check if ‘V’ is not visited.
- Update value of ‘D’ by adding ‘T’ to it.
- Call DFS function on the node ‘V’ with ‘PRE’ value equal to ‘T’.
- Else
- Update value of ‘D’ by adding ‘PRE’ to it to add the time taken to travel back again.