Programming Geek
Rated 4.1/5 based on 446 reviews

TCS CodeVita 2015 Round 2 : TestVita

Problem : TestVita

TCS is working on a new project called "TestVita". There are N modules in the project. Each module (i) has completion time denoted in 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 Project manager, you are asked to deliver the project as early as possible.
Provide an estimation of amount of time required to complete the project.
Input Format:

First line contains T, number of test cases.

For each test case: 
  1. First line contains N, number of modules.
  2. Next N lines, each contain:
    • (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. 1 <= T <= 10
2. 0 < N < 1000; number of modules
3. 0 < i <= N; module ID 
4. 0 < Hi < 60; number of hours it takes to complete the module i
5. 0 <= |D| < N; number of dependencies
6. 0 < Dk <= N; module ID of dependencies

Sample Input and Output

SNo.InputOutput
1
1
5
1 5
2 6 1
3 3 2
4 2 3
5 1 3

16


Note:

Please do not use package and namespace in your code. For object oriented languages your code should be written in one class.
Note:

Participants submitting solutions in C language should not use functions from / as these files do not exist in gcc
Note:

For C and C++, return type of main() function should be int.