Pueblo Nuevo


Submit solution

Points: 100 (partial)
Time limit: 5.0s
Memory limit: 256M

Authors:
Problem types
Allowed languages
C, C++

Sekai ha ido de visita a Matanzas nuevamente y quiere visitar a sus amigos de Pueblo Nuevo. Hay n casas de amigos en Pueblo Nuevo y k de ellas son las más importantes para él. Hay m 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 k casas de amigos más importantes están conectadas con caminos renovados.

Subtareas

En todas las subtareas se cumple que 1 \leq c \leq 10^{9} y n \geq k.

  • Subtarea 1 (22 puntos): 2 \leq k \leq 5, n \leq 20, 1 \leq m \leq 40.
  • Subtarea 2 (14 puntos): 2 \leq k \leq 3, n \leq 10^{5}, 1 \leq m \leq 2*10^{5}.
  • Subtarea 3 (15 puntos): 2 \leq k \leq 4, n \leq 1000, 1 \leq m \leq 2000.
  • Subtarea 4 (23 puntos): k=4, n \leq 10^{5}, 1 \leq m \leq 2*10^{5}.
  • Subtarea 5 (26 puntos): k=5, n \leq 10^{5}, 1 \leq m \leq 2*10^{5}.

Entrada

La primera línea contiene tres enteros n, k, m: 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 1, 2, \dots, n.

La segunda línea contiene k enteros: las casas de amigos importantes.

Finalmente la entrada contiene m líneas que describen las calles. Cada una contiene tres enteros a, b, c que quiere decir que hay una calle entre las ciudades a y b y cuesta c 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

There are no comments at the moment.