Verificando una coartada.
Un crimen ha sido cometido. Una carga de grano ha sido tomada del establo por una de las vacas de GJ. GJ está tratando de determinar cual de sus vacas es la culpable. Afortunadamente, un satélite que pasaba por la zona tomó una imagen de su granja segundos antes que el crimen tuviera lugar, dando la ubicación de todas las vacas. El quiere saber cuales vacas tenían tiempo para llegar al establo y robar el grano.
La granja del Granjero Juan comprende campos numerados que están conectados por caminos bidireccionales cuyo tiempo de recorrido está en el rango segundos (las vacas caminan muy despacio). El campo contiene al establo. No toma ningún tiempo desplazarse dentro de un campo.
Dada la distribución de la granja del Granjero Juan y la ubicación de cada vaca cuando el satélite pasó por encima, determine el conjunto de vacas que podrían ser culpables.
Entrada
Línea Cuatro enteros separados por espacios: , , y .
Líneas Tres enteros separados por espacios describiendo un camino: , y . El camino conecta y y se requieren segundos para recorrerlo.
Líneas Un entero por línea, la ubicación de una vaca. La primera línea da el número del campo donde está la vaca 1, la segunda de la vaca 2, etc.
Ejemplo de Entrada
7 6 5 8
1 4 2
1 2 1
2 3 6
3 5 5
5 4 6
1 7 9
1
4
5
3
7
Detalles de la Entrada
Campos/distancias como esto:
6
4------5
| |
2| |
| |
7-----1 |5
9 | |
1| |
| |
2------3
6
Salida
Línea Un solo entero , el numero de vacas que podrían ser culpables del crimen.
Líneas Un solo número de vaca en cada línea que es una de las vacas que podrían ser culpables del crimen. La lista debe estar en orden ascendente.
Ejemplo de Salida
4
1
2
3
4
Detalles de la Salida
Cualquier vaca, excepto la 5 podría haberlo hecho. A la vaca 5 le hubiera tomado 9 segundos llegar al establo.
Comments
Ojo: Por si le sirve a alguien, hay juegos de datos donde entre un mismo par de campos hay varios caminos. Esto puede traer problemas para algunas estructuras de datos que suelen usarse para los grafos.