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!