All submissions for this problem are available.
A terrorist group SRPY is thinking of destroying a country named JTRT. JTRT has N cities connected by E bidirectional roads. Cities are designated city number starting from 0 till N-1 . The group have decided to use bombs for causing destruction , but the group has one problem that is they have only B number of bombs with them . After gathering information about the population of each city the group placed B number of bombs in those cities that have city number in the range from 0 to B-1 ( both 0 and B-1 included ) for causing maximum destruction as these cities have maximum population .
The police got to know about this and they started thinking of diffusing the bombs as quickly as possible. The police decided to call one bomb squad team but there were only three city in which the bomb squad team was present and these three city has city number r1 , r2 , r3 . All the three bomb squad team are present in cities in which bomb is not placed .The police was having difficulty in figuring out which one out of the three teams should be sent for diffusing bombs very quickly .
So the police called one of the ACM member who quickly calculated and told the police which bomb squad will take minimum time to travel from the city in which that squad is located to all the cities in which bombs are placed . The police followed what the member said and sent the squad which took minimum time out of three squad and ultimately all bomb were diffused.
Assuming you were ACM member how would you calculate the minimum time of travelling .
First line contain t denoting number of test cases.
The first line of a test case contains two numbers N and E.Then E lines follow each line having three numbers a , b , c. a & b are city number c = time to travel between the city a and the city b .
Then a line is present which contains B , r1 , r2 , r3.
Print the minimum time ( of travelling ) corresponding to the squad which was sent as given in the question.
- 0 < t ≤ 10
- 0 < N ≤ 10000
- 0 < E ≤ 30000
- 0 < c ≤ 10
- 0 < B ≤ 6
INPUT: 2 7 6 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 3 4 5 6 5 4 0 1 1 0 2 2 0 3 3 0 4 4 2 3 4 2 OUTPUT: 10 3
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.