Verificando una coartada.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C#, C++, Java, Pascal, Python, VB

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 C (1 \leq C \leq 100) vacas es la culpable. Afortunadamente, un satélite que pasaba por la zona tomó una imagen de su granja M (1 \leq M \leq 70000) 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 F (1 \leq F \leq 500) campos numerados 1...F que están conectados por P (1 \leq P \leq 1,000) caminos bidireccionales cuyo tiempo de recorrido está en el rango 1...70000 segundos (las vacas caminan muy despacio). El campo 1 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 1: Cuatro enteros separados por espacios: F, P, C y M.

  • Líneas 2...P+1: Tres enteros separados por espacios describiendo un camino: F_1, F_2 y T. El camino conecta F_1 y F_2 y se requieren T segundos para recorrerlo.

  • Líneas P+2...P+C+1: 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 1: Un solo entero N, el numero de vacas que podrían ser culpables del crimen.

  • Líneas 2...N+1: 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


  • 1
    yosva13  commented on Jan. 31, 2024, 8:42 p.m. edited

    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.