Pueblo Nuevo
Sekai ha ido de visita a Matanzas nuevamente y quiere visitar a sus amigos de Pueblo Nuevo. Hay casas de amigos en Pueblo Nuevo y de ellas son las más importantes para él. Hay calles conectando las casas. Desafortunadamente las calles están en tan malas condiciones que Sekai no puede ir a toda velocidad en su bicicleta por ellas. Así que pensó en la siguiente situación.
Conociendo el costo de renovar cada calle, cuál es el costo mínimo de renovar un conjunto de calles de tal manera que las casas de amigos más importantes están conectadas con caminos renovados.
Subtareas
En todas las subtareas se cumple que y .
- Subtarea 1 (22 puntos): , , .
- Subtarea 2 (14 puntos): , , .
- Subtarea 3 (15 puntos): , , .
- Subtarea 4 (23 puntos): , , .
- Subtarea 5 (26 puntos): , , .
Entrada
La primera línea contiene tres enteros : el número de casas de amigos, el número de casas de amigos importantes y el número de calles respectivamente. Las casas están enumeradas .
La segunda línea contiene enteros: las casas de amigos importantes.
Finalmente la entrada contiene líneas que describen las calles. Cada una contiene tres enteros que quiere decir que hay una calle entre las ciudades y y cuesta renovarla.
Puede asumir que siempre habrá un camino entre cualquier par de ciudades.
Salida
Imprima el mínimo costo de renovar un conjunto de carreteras de tal manera que Sekai pueda ir en bicicleta entre todas las casas de amigos importantes.
Ejemplos
Entrada 1
4 3 6
1 3 4
1 2 4
1 3 9
1 4 6
2 3 2
2 4 5
3 4 8
Salida 1
11
Comments