3384 - C2 - Happiness for All 3384 - Directo a la Felicidad 3384 - C2 - Happiness for All

Statistics Sub: 220 | AC: 140 | AC%: 63,64 | Score: 1,30
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 20000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The separatist state of Nlogonia has N cities numbered from 1 to N. Some pairs of cities are connected by highways, so that if there is a highway between city A and city B it is possible to travel from A to B or from B to A. We say that a citizen from city i can visit another from city j if there exists a sequence of different cities c[1], c[2], ..., c[m] with m >= 2 such that c[1] = i, c[m] = j and there is a highway between cities c[k] and c[k+1] for k = 1, 2, ..., m-1.

The people of Nlogonia are very sociable, so they have friends in all the cities they can visit. However, they are also a bit lazy, so that they are not happy unless they can visit each of their friends by taking exactly one highway directly from their city to their friend's.

To avoid Nlogonia's scission, the queen has decided to perform a number of infrastructure works in order to make all of its citizens happy. One possibility consists in building new highways between the cities of Nlogonia, incurring in a cost of R per new highway built. Because building many highways can be very expensive, another possibility is to build stadiums in some of Nlogonia's cities. The building of a stadium costs E, and immediately makes all the citizens happy in the city where it is built. Then again, you should know that Nlogonia's inhabitants are furthermore somewhat jealous, so that they shall never be happy if there is no stadium in their own city, but there is one in some of their friend's cities. Can you help the queen calculate the minimum cost of the construction work necessary to make everyone in Nlogonia happy?
El estado separatista de Nlogonia tiene N ciudades numeradas del 1 al N. Algunos pares de ciudades están conectados por rutas, de modo tal que si hay una ruta entre la ciudad A y la ciudad B es posible trasladarse desde A a B, o viceversa desde B a A. Decimos que un habitante de la ciudad i puede visitar a otro de la ciudad j si existe una secuencia de ciudades distintas c[1], c[2], ..., c[m] con m >= 2 tal que c[1] = i, c[m] = j y hay una ruta entre las ciudades c[k] y c[k+1] para k = 1, 2, ..., m-1.

Los habitantes de Nlogonia son muy sociables, por lo que tienen amigos en todas las ciudades que pueden visitar. Sin embargo, también son algo perezosos, de modo que no son felices salvo que puedan visitar a cada uno de sus amigos tomando exactamente una ruta directamente desde su ciudad hasta la del amigo en cuestión.

Para evitar la escisión de Nlogonia, la reina ha decidido llevar a cabo un conjunto de obras para lograr que todos sus habitantes sean felices. Por un lado, puede ordenar la construcción de nuevas rutas entre las ciudades de Nlogonia, incurriendo en un costo R por cada nueva ruta que se construya. Por otro lado, como construir muchas rutas puede llegar a ser muy caro, también pueden construirse estadios en algunas de las ciudades de Nlogonia. La construcción de un estadio tiene un costo E, y hace inmediatamente felices a todos los habitantes de la ciudad en la que se lleva a cabo la construcción. Sin embargo, hay que tener en cuenta que los habitantes de Nlogonia son además algo celosos, de modo que no serán felices si no hay un estadio en su ciudad pero sí en la de alguno de sus amigos. ¿Pueden ayudar a la reina a calcular el mínimo costo de las obras necesarias para lograr que todos los habitantes de Nlogonia sean felices?
The separatist state of Nlogonia has N cities numbered from 1 to N. Some pairs of cities are connected by highways, so that if there is a highway between city A and city B it is possible to travel from A to B or from B to A. We say that a citizen from city i can visit another from city j if there exists a sequence of different cities c[1], c[2], ..., c[m] with m >= 2 such that c[1] = i, c[m] = j and there is a highway between cities c[k] and c[k+1] for k = 1, 2, ..., m-1.

The people of Nlogonia are very sociable, so they have friends in all the cities they can visit. However, they are also a bit lazy, so that they are not happy unless they can visit each of their friends by taking exactly one highway directly from their city to their friend's.

To avoid Nlogonia's scission, the queen has decided to perform a number of infrastructure works in order to make all of its citizens happy. One possibility consists in building new highways between the cities of Nlogonia, incurring in a cost of R per new highway built. Because building many highways can be very expensive, another possibility is to build stadiums in some of Nlogonia's cities. The building of a stadium costs E, and immediately makes all the citizens happy in the city where it is built. Then again, you should know that Nlogonia's inhabitants are furthermore somewhat jealous, so that they shall never be happy if there is no stadium in their own city, but there is one in some of their friend's cities. Can you help the queen calculate the minimum cost of the construction work necessary to make everyone in Nlogonia happy?

Input specification

The first line contains four integers N, M, R and E. The number N represents the number of cities in Nlogonia (2 <= N <= 1000), M represents the original number of highways (1 <= M <= 10^5), whereas R and E represent the cost of building a highway and a stadium, respectively (1 <= R, E <= 1000). Each of the following M lines describes a different highway using two integers A and B, representing the cities connected by said highway (1 <= A, B <= N with A ≠ B).
La primera línea contiene cuatro enteros N, M, R y E. El entero N representa la cantidad de ciudades en Nlogonia (2 <= N <= 1000), M representa la cantidad de rutas que hay originalmente (1 <= M <= 10^5), mientras que R y E representan el costo de construcción de una ruta y un estadio, respectivamente (1 <= R, E <= 1000). Cada una de las siguientes M líneas describe una ruta distinta mediante dos enteros A y B, que representan las ciudades que son conectadas por dicha ruta (1 <= A, B <= N con A B).
The first line contains four integers N, M, R and E. The number N represents the number of cities in Nlogonia (2 <= N <= 1000), M represents the original number of highways (1 <= M <= 10^5), whereas R and E represent the cost of building a highway and a stadium, respectively (1 <= R, E <= 1000). Each of the following M lines describes a different highway using two integers A and B, representing the cities connected by said highway (1 <= A, B <= N with A ≠ B).

Output specification

Print one line containing an integer representing the minimum cost of the construction work necessary to make everyone in Nlogonia happy.
Imprimir en la salida una línea conteniendo un entero que representa el mínimo costo de las obras necesarias para lograr que todos los habitantes de Nlogonia sean felices.
The first line contains four integers N, M, R and E. The number N represents the number of cities in Nlogonia (2 <= N <= 1000), M represents the original number of highways (1 <= M <= 10^5), whereas R and E represent the cost of building a highway and a stadium, respectively (1 <= R, E <= 1000). Each of the following M lines describes a different highway using two integers A and B, representing the cities connected by said highway (1 <= A, B <= N with A ≠ B).

Sample input

9 6 11 12
1 2
3 2
4 5
5 6
6 7
9 7

Sample output

71

Hint(s)

http://coj.uci.cu/24h/
http://coj.uci.cu/24h/
http://coj.uci.cu/24h/

Recommendation

We have carefully selected several similar problems: 2824 | 1946 | 2191 | 2105 | 2740 | 2412