Travel Nodes

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.

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].

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.

We start from node 1. Its adjacent nodes are: {2, 3, 4} out of which node 4 has maximum weight, so the first arrival time at node 4 will be 5 units (time taken to reach node 4 from node 1) We then move to node 4 whose adjacent nodes are: {1, 3} out of which we have already visited node 1, so we move to node 3, so the first arrival time at node 3 will be 5 + 3 = 8 (previous time + time taken to reach node 3 from node 4). We then move to node 3 whose adjacent nodes are: {1} which is already a visited node. We then travel back to node 1, which takes 8 units of time. 8 + 8 = 16 units. We then move to node 2 from node 1, which takes 16 + 4 = 20 units.

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.

Depth - First Search

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.

Time Complexity

O(N*(N + M)), where ‘N’ is the number of nodes, and ‘M’ is the number of edges.

In each recursive call, we traverse all the adjacent nodes of the current node to find the next node according to the conditions which take O(N + M) of time. The total number of recursive calls for a vertex can be maximum up to N. The total number of vertices is ‘N’, and the total number of edges is ‘M’. Therefore, the overall time complexity will be O(N*(N + M)).

Space Complexity

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

For each vertex, we store its adjacent vertices; therefore, storing them in the form of a graph will require O(N + M) space. In the worst case of a fully connected graph, there will be an edge between each vertex, making O(N^2) space. We also use the ‘VISITED’ array, which all require O(N) space. The recursive stack of the DFS function will contain all the neighbors of a vertex, which at most can be ‘N’ vertices. Therefore, the overall space complexity will be O(N^2).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation For Sample Input 1 :

Sample Input 2 :

Sample Output 2 :

Explanation For Sample Input 2 :