Java and Haskell
All submissions for this problem are available.
The kingdoms of Java and Haskell are at war with each other. To win the war, Haskell needs to disrupt the communication between the financial and the administrative capital cities of Java named UTIL and LANG. There are m strategic points(towns or cities) in the kingdom of Java. There is no direct road between the cities UTIL and LANG. The communication between the two cities is by means of roads passing through strategic points. There is AT MOST one direct road between any two strategic points. Every road has a single bridge. There is a cost associated with blowing up a bridge or bribing a town's mayor to stop all traffic passing through the town. Both the cities can communicate with each other if there is at least one sequence of roads with non-blown up bridges and non-bribed towns that leads from one city to the other. Your task is to find the minimum cost that Haskell has to spend to disrupt the communication between the capital cities of Java. Assume that the city heads of UTIL and LANG can't be bribed.
First line of input is number of test cases T, after which T test cases follow. Each test case specifies two integers m(number of strategic points) and n(number of roads) on the first line separated by space. After that m-2 lines follow each corresponding to town numbers 2 through m-1 in serial order, containing one integer b that denotes the bribe required to be paid to its mayor for closing the communication through that town. Afterwards n lines follow, each containing 3 space separated integers u, v and c; where u and v are the town numbers through which the road passes and c is the cost of blowing up the bridge on that road. UTIL and LANG have strategic point IDs of 1 and m respectively.
For each test case output a single line containing a single integer i.e. the minimum cost of disrupting communication between UTIL and LANG for that test case. Output 0 for a case when the communication is already disrupted between the two cities.
- 1 ≤ T ≤ 100
- 1 ≤ m ≤ 50
- 1 ≤ n ≤ 100
Input: 2 4 4 2 5 3 1 3 4 3 3 4 2 1 2 1 3 4 4 2 2 2 1 3 3 1 3 4 2 1 4 3 3 Output: 4 3
|Time Limit:||0.164659 sec|
|Source Limit:||50000 Bytes|
|Languages:||ASM, BASH, C, C99 strict, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, GO, HASK, JAVA, JS, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.