1193 - Panda Land 5: Panda Programming Language
Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 34
Solved: 14
- Description
- Unlike in human world, panda world has only one programming language, it is Panda Programming Language (PPL). This language is developed by Panda Bureau of Technology (PBT), one of the government special department.
This language is built based on procedural programming rule, so it is completely possible to create more than one function on a program. Unfortunately, this language lacks of function prototyping ability. That means each function should have been defined before it can called by any other function. Recursive call is allowed in PPL.
Currently PBT is too busy to build that feature. Meanwhile, there is a certain program that need to be compiled. The programmers wrote that program without taking the function definition sequence in consideration (ie. some functions are not defined before other function that call them). So, they came to human world and found you, the best programmer on earth! They need your help to write a specific program that can rearrange their program so it can be compiled. But they have one more problem, their programming environment are not so friendly as yours, so the total cost of rearrangement should be minimized!
The cost of moving a certain function is calculated by multiplying the number of line of that function to the total number of skipped line. For example, let there are four functions defined as A, B, C and D (A at the top and D at the bottom) which have 10, 4, 6 and 3 lines respectively. Moving A below D will cost A * (B + C + D) = 10 * (4 + 6 + 3) = 130. Moving D above B (between A and B) will cost D * (C + B) = 3 * (6 + 4) = 30.
- Input
- The first line of input contains an integer T, the number of test cases follow.
Each case begins with an integer N (1 <= N <= 18), the number of function. The next line contains N integers (1 <= Mi <= 100) representing the number of line for each function i = 1 ... N. The next N lines each will describes ith function dependency. Each line will start with an integer C (0 <= C < N), the number of other function that is called by that ith function. Next will be C integers (1 <= Fj <= N) representing the function which it needs. The last line for each case will contains N integers representing be the initial function definition. - Output
- For each case, print in a single line the minimum cost needed to rearrange that program so it can be compiled, or print "-1" if there is no such arrangement.
- sample input
-
2 4 7 3 12 8 1 3 1 4 2 1 3 0 1 2 3 4 5 7 3 12 8 4 3 1 2 4 0 1 2 0 1 4 1 2 3 4 5
- sample output
-
-1 161
- hint
- source