Tiempo máximo: 4000 ms
Memoria máxima: 64000 KB
Dificultad: Medio (55)
Tomás y Danimania quedan para ir en bici. Para que ninguno tenga que recorrer una distancia mucho mayor que el otro, acuerdan una distancia umbral \(d\). Viven en una ciudad con \(n\) lugares conectados por \(m\) calles bidireccionales, cada una con una longitud en kilómetros. Quieren elegir uno o varios puntos de encuentro tales que la diferencia entre la distancia que tiene que recorrer cada uno hasta ese punto sea como máximo \(d\). Tu tarea es ayudarles a encontrar todos los posibles puntos de encuentro justos, respondiendo a varias consultas con diferentes pares de ubicaciones para Tomás y Danimania.
La entrada está compuesta por varias líneas: - La primera línea contiene tres enteros \(n\), \(m\) y un número real \(d\) - el número de lugares, el número de carreteras, y la distancia umbral. - Luego siguen \(n\) líneas, cada una con el nombre único de cada lugar (no contienen espacios). - Luego siguen \(m\) líneas, cada una con tres valores: \(u\), \(v\) y \(w\), indicando que hay una calle bidireccional entre el lugar \(u\) y el lugar \(v\) de longitud \(w\) kilómetros. - Luego sigue un entero \(q\) - el número de consultas a realizar. - Finalmente siguen \(q\) líneas, cada una con los nombres de los lugares de origen y destino de ambos.
Por cada consulta, imprime un entero \(k\): el número de lugares que pueden ser puntos de encuentro justos. Después, imprime \(k\) líneas, cada una con el nombre de un lugar válido, en orden lexicográfico. Un lugar es un punto de encuentro justo si la diferencia entre las distancias que tienen que recorrer Tomás y Danimania es menor o igual que \(d\). Para evitar errores de precisión con decimales, considera que las distancias y la diferencia se tratan con precisión de dos decimales.
Ejemplo 1
Entrada
7 8 1.5 Marxalenes Alameda Oceanografic UPV UV Reus PontDeFusta Marxalenes Alameda 1.0 Alameda Oceanografic 2.0 Alameda UPV 1.0 UPV UV 9.0 UV Reus 8.0 Reus PontDeFusta 2.0 PontDeFusta Marxalenes 5.0 Oceanografic UPV 1.0 3 Marxalenes Oceanografic UPV UV Reus PontDeFusta
Salida
3 Alameda UPV UV 1 Reus 0