Fanatic, the leader of terrorist organization (whose name is too secret to be mentioned here), had decided to launch attacks in different cities of the U.S. However, CTU (Counter Terroris Unit) has established a strong supportive network between major cities. Consider the cities of concern as nodes in graph, and roads in between cities are bidirectional edges on the graph. Each edge has a "length", which correspond to the time required to travel the road. A counter-terrorist supportive network is a set of roads, such that together they form a tree connecting all the cities, and the "sum of length" of the network is defined as the sum of costs of edges in the chosen set. Clearly, the smaller the sum of length, the safer the network since when a city is attacked, support from other cities are likely to come sooner. Thus, in this sense we can define the "best" counter-terrorist network (possibly not unique) to be the network with smallest sum of length.
Under executive of CTU - Jack's command, all such "best" counter-terrorist network are found and prepared, so that when some road is obstructed or destroyed for particular reason, backup networks could be used. Fanatic, on the other hand, knows all about the supportive network. Therefore he decides to sabotage all the viable "best" networks before he could take any further move. To do so, he chooses some of the roads used in the networks and bombing it, effectively stopping anything from passing through the road. A network is said to be "sabotaged" if at least one of its road is bombed. There is one complication though, the "cost" required to bomb a particular road (factoring in money, safety ... etc) may be different for each road. And of course, Fanatic would want the cheapest solution.
Now, given the cities and connections among them, what is the minimum cost Fanatic must spend in destroying roads in order to compromise all the "best" counter-terrorist networks?
| 05:00:00 |
Whoops, time is ticking, better solve the problem now!
There may be multiple testcases for this problem.
Each testcase starts with a pair of integers N (2 <= N <= 300), M (M <= 10000), indicating the number of cities and roads, respectively.
Following is M lines of descriptions of the roads in the form vi, ui, li, ci, representing the two endpoints, the length of the road, and the cost to sabotage it. Cities are numbered from 0 to N-1. The cost and length of a road will not exceed 100000.
The input graph is guaranteed to be connected.
Other than this, do not assume any special property from the input graph.
For each testcase, output the minimum cost to sabotage the CTU supportive network.
8 12 0 1 2 5 1 2 4 5 1 3 2 5 1 4 3 2 3 5 3 4 4 5 2 5 4 7 2 5 4 6 4 5 0 3 2 1 5 7 2 1 0 5 6 3 2 6 4 2
6
Migrated from old NTUJ.
kelvin
| No. | Testdata Range | Score |
|---|