# Graph Traversal with Tree-Like Structure

We have a graph which looks similar to a tree structure, like that. In particular, the nodes are only connected to their nodes below.

``````    Node   Node
/    \  /  \
Node  Node   Node
\     \
Node   Node
``````

The input for such (but not the one above) graph looks like that:

4 5
1 2 10
2 3 20
1 4 10
3 4 25
2 4 30

In the first line, we have the 4, which specifies that we have 4 nodes in the graph. 5 means, we have 5
edges. The following lines (1, 2, 10), (2, 3,20)… read as follows:

There is an edge from Node 1 to Node 2 with the cost of 10
There is an edge from Node 2 to Node 3 with the cost of 30 and so on.
The goal is to find the highest cost for any path in the graph.

The output, or the max cost would be by traversing the path (1 → 2 → 3 → 4) and would give a cost of 55.

I tried to code it and came up with this:

``````T = int(input())

def dfs(graph, node, dp, visited):

cur, dist = node[0], node[1]
visited[cur] = True
for neighbor in graph[cur]:
n_idx, n_dist = neighbor[0], neighbor[1]
if not visited[n_idx]:
dfs(graph, neighbor, dp, visited)
dp[cur] = max(dp[cur], dp[n_idx] + n_dist)

res[0] = max(res[0], dp[cur])

for j in range(T):
vertices, edges = [int(x) for x in input().split()]
graph = [[] for _ in range(vertices + 1)]
dp = [0] * (position + 1)
for _ in range(vertices):
node = [int(y) for y in input().split()]
node_idx = node[0]
graph[node_idx].append((node[1], node[2]))

res = [0]
visited = [False] * (position + 1)
for i in range(1, position + 1):
if not visited[i] and len(graph[i]) > 0:
dfs(graph, (i, 0), dp, visited)

print(f"Case #{j + 1}: {res[0]}")
``````

This code returns a run error, and exceeds time limit if I remove the

``````
if not visited[n_idx]:
dfs(graph, neighbor, dp, visited)
``````

condition in the DFS function. I would really appreciate any help!

Where did you define/declare the variable `position`?

That is actually a typo and should be the vertices. I just forgot to translate it. I have fixed it