Trader Dogy
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 34 Accepted Submission(s): 3
Problem Description
Trader Dogy lives in a city consists of n districts. There are n - 1 bidirectional roads in the city, each connecting a pair of districts. It is guaranteed that Dogy can reach every district regardless of district to start with.
One day Dogy is assigned a task with high awards. In this task, Dogy needs to visit a list of K districts one by one, in order to buy and sell some goods. It takes a lot of time, so Dogy wants to make good use of his car. Let Targeti be the i-th district in the list. Initially Dogy is in the district with number Target1 with his only car.
At any time, Dogy can pass a road by car or park his car at the district he is currently in and try other transportations (which means he can not drive his car until he comes back to the district where he parks his car). Also, he can not park his car on roads.
More precisely, the for the i-th road connecting city ai and bi, it will take costCari units of time to pass by car, or costOtheri to pass in other ways of transportations. Please note that costCari might be larger than costOtheri due to traffic congestion.
Now Dogy turns to you for help. He asks you to make a plan minimizing the total time required for his task. As his best friend, can you solve the problem?
One day Dogy is assigned a task with high awards. In this task, Dogy needs to visit a list of K districts one by one, in order to buy and sell some goods. It takes a lot of time, so Dogy wants to make good use of his car. Let Targeti be the i-th district in the list. Initially Dogy is in the district with number Target1 with his only car.
At any time, Dogy can pass a road by car or park his car at the district he is currently in and try other transportations (which means he can not drive his car until he comes back to the district where he parks his car). Also, he can not park his car on roads.
More precisely, the for the i-th road connecting city ai and bi, it will take costCari units of time to pass by car, or costOtheri to pass in other ways of transportations. Please note that costCari might be larger than costOtheri due to traffic congestion.
Now Dogy turns to you for help. He asks you to make a plan minimizing the total time required for his task. As his best friend, can you solve the problem?
Input
There are several test cases. Please process till EOF.
Each test case contains several lines, for each test case,
The first line contains two integers n, K(1 ¡Ü n, K ¡Ü 100000) where n is the number of districts and K is the length of the list mentioned above.
The following n - 1 lines describes roads, each containing 4 numbers ai, bi, costOtheri, costCai.
The last line contains K integers: the elements in the list.
One useful tip: The structure of Dogy¡¯s city is randomly generated, see Hint below for more details.
Hint:
The data generator for this problem runs as follows: for each i > 1, it creates a road connecting districti and districtrandint(1,i - 1), where randint(l, r) returns an integer uniformly distributed between l and r, inclusively.
Each test case contains several lines, for each test case,
The first line contains two integers n, K(1 ¡Ü n, K ¡Ü 100000) where n is the number of districts and K is the length of the list mentioned above.
The following n - 1 lines describes roads, each containing 4 numbers ai, bi, costOtheri, costCai.
The last line contains K integers: the elements in the list.
One useful tip: The structure of Dogy¡¯s city is randomly generated, see Hint below for more details.
Hint:
The data generator for this problem runs as follows: for each i > 1, it creates a road connecting districti and districtrandint(1,i - 1), where randint(l, r) returns an integer uniformly distributed between l and r, inclusively.
Output
For each test case, print one integer: the cost of time in your minimized plan.
Sample Input
4 3 1 2 1 100 2 3 100 1 2 4 1 100 1 3 4
Sample Output
103