Cable TV

You would like to provide citizens of a newly constructed neighborhood with cable television.
As a computer scientist, you know this calls for... wires!

Surveyors have done their work and have given you the cost of connecting pairs of locations.
However, they have also warned you that certain links might be dangerous - there is a risk of interference from power lines and such.
Find the minimum cost to connect all the houses, minimizing the cost but above all minimzing the number of dangerous links used.


N ≤ 100, the number of locations.
M ≤ 10000, the number of possible links.
M lines, each with four integers a,b,c,d.
Each line signifies a possible (bidirectonal) link between locations a and b, with cost c. d will be 1 if the link is dangerous, and 0 otherwise.


Two integers.
Output a) the minimum number of dangerous links required and b) the total minimum cost.

Sample Input

4 4
1 2 2 0
2 3 1 1
3 1 1 0
3 4 1 1

Sample Output

1 4

Take 1-2, 3-1, and 3-4.
The use of one dangerous cable is inevitable, but we can avoid the use of the other.

All Submissions
Best Solutions

Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Mar 04, 2009

Problem Types: [Show]

Languages Allowed:

Comments (Search)

Is it possible that we have both a dangerous and non-dangerous edges on the same edge? For example:

1 2 10 0
1 2 20 1

It was not stated in the problem.

The way the problem is stated implies that there can only be one set of <cost, danger> for any pair of locations, so no, it cannot be both dangerous and safe to connect a pair of locations. (Nor can it cost both 10 and 20.)

That said, a well-written solution should not care that there are multiple possible links.

For reference, costs definitely do not exceed 1000, as verified by submission 183909. I point this out only because of the content in the analysis.

Do we separately calculate for minimal danger and minimal cost, or do we calculate both for the same case prioritizing danger over cost?