EC_MODE - Modems


A Oruro province wants ALL the towns to have Internet access and to communicate with each other by at least one channel (not necessarily direct). The engineer in charge asks you to help him determine the minimum cost of providing this access.

There are N towns in total (1 <= N <= 1000). UTP can be used only up to range R (1<=R<=10000). If this distance is exceeded, optical fiber must be used instead. The unit cost of using UTP cable is U and the unit price of the optical fiber is V (U <= V; 1 <= U, V <= 10). There are also W satellite modems purchased (1 <= W < N). These satellite modems can be placed in any town. Satellite modem will allow a town to use the internet and communicate with any other modem in the province.

Input

The first line contains the number of test cases. First line of each test case consists of five integers N, R, W, U, V. Then N lines follow, each with integer pair xi, yi (-10000 <= xi, yi <= 10000), the coordinates of i-th town.

Output

For each case, print a line of the form:

Caso #TC: A B

Where TC is the test case number, A is the total cost of using UTP cable and B is the total cost of using optical fiber. Print both A and B rounder to 3 decimal places.

Example

Input:
2
3 1 1 1 1
0 0
0 1
1 0
6 1 3 2 3
0 0
0 2
2 0
3 2
2 3
3 3

Output:
Caso #1: 2.000 0.000
Caso #2: 4.000 6.000

hide comments
jdmoyle: 2021-09-14 08:48:05

Hints:
1. Distances are calculated as in a 2D plane;
2. The cost depends on the distance.
3. If components of the graph equals W or 1 break;

princemishra: 2021-07-02 06:57:21

here w means that you can make w connected components in place of a single connected component =>
in place of a tree u can make w disjoint trees (w groups of towns)

nyawriter: 2020-05-01 08:42:12

[solved]

Last edit: 2020-05-01 08:43:42
riyadhrazzaq: 2018-10-01 09:15:48

The need for W seems unclear at first. If you get TLE for checking number of subgraph using disjoint set then just count the number of road taken in mst and subtract from total number of town. This will return the subgraphs in forrest.
@sifat_15, Total 3 towns. Distance between each of them is calculated using rules of distance between two point in a graph. if distance is greater than R, weight of that road is V, else U. After building road between all towns, simple Kruskal/Prims will suffice.

sifat_15: 2018-08-21 19:52:30

Can anyone please explain 1st test case ??

jayantisswani: 2017-09-29 18:39:20

How is the cost calculated? Does the cost depend on the distance? The question is not clear and neither the testcases make it clear.

nsitsk: 2016-10-15 19:25:14

Please note the "Caso" and not "Case" in output. Costed me 3 WA's. :(

avisheksanvas: 2016-07-28 21:18:07

MST is getting fun! :)

kejriwal: 2015-12-14 15:00:20

use scanf()/printf() in cpp...cout/cin give WA(T_T) !!

Mitch Schwartz: 2014-09-16 08:55:51

For those who were confused by the problem statement (as I was at first):

1) "Satellite modem" and "modem" are the same thing.
2) Every town must either have a modem or be connected to a town that has a modem.

Last edit: 2014-01-14 01:01:59

Added by:Eddy Cael
Date:2013-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CSHARP CPP C++ 4.3.2 HASK JAVA PAS-FPC PYTHON RUBY
Resource:Competencia CCBOL 2013