Problem Statement:
TCS is working on a new project called “Testvita“. There are N modules in the project. Each module i has a completion time denoted in the number of hours Hi and may depend on other modules. If module x depends on module y then one needs to complete y before x.
As a project manager, you are asked to deliver the project as early as possible. Provide an estimation of the amount of time required to complete the project.
Input Format:
The first line contains T, the number of test cases.
For each test case:
- The first line contains N, the number of modules.
- Next N lines, each contains:
- i – module id
- Hi – number of hours it takes to complete the module
- D – set of module ids that i depends on – integers delimited by space
Output Format:
Output the minimum number of hours required to deliver the project.
Constraints:
- 1 <= T <= 10
- 0 < N < 1000; number of modules
- 0 < i <= N; module Id
- 0 < Hi < 60; number of hours it takes to complete the module i
- 0 <= |D| < N; number of dependencies
- 0 < Dk <= N; module Id of dependencies
Example 1:
Input: 1 5 1 5 0 2 6 1 3 3 2 4 2 3 5 1 3 Output: 16
Code:
Java
C++
Python
from collections import deque def testvita(n, hours, in_degree, graph): queue = deque() total_hours = [0] * (n + 1) max_time = 0 for key, value in in_degree.items(): if value == 0: total_hours[key] = hours[key] queue.append(key) while queue: curr_module_id = queue.popleft() for nbr in graph[curr_module_id]: if nbr != 0: in_degree[nbr] -= 1 if in_degree[nbr] == 0: queue.append(nbr) total_hours[nbr] = total_hours[curr_module_id] + hours[nbr] max_time = max(max_time, total_hours[nbr]) return max_time if __name__ == '__main__': testcases = int(input()) for t in range(testcases): n = int(input()) # number of modules hours = dict() # completion time of each module graph = dict() # module_id : [list of neighbors] in_degree = dict() # in degree of each node for node in range(1, n + 1): in_degree[node] = 0 graph[node] = list() for i in range(n): module_info = list(map(int, input().split())) module_id = module_info[0] module_completion_time = module_info[1] module_prerequisites = module_info[2 : ] hours[module_id] = module_completion_time for nbr in module_prerequisites: if nbr != 0: graph[nbr].append(module_id) for nbr in module_prerequisites: if nbr != 0: in_degree[module_id] += 1 ans = testvita(n, hours, in_degree, graph) print(ans)