uCoder | 1257 | Nível: 5 | Tempo Limite: 10
Usina
Adaptado por Erich Rodrigues
Competição: OBI 2015, Nível 2, Fase 2
A Usina Nuclear Indiscutivelmente Campeã (Unicamp) é organizada em N salas numeradas de 1 a N . Por questões de segurança, o reator fica no subsolo, na sala de número N , e é monitorado por um técnico. No passado, a sala de controle ficava logo ao lado do reator, mas os engenheiros estavam desconfortáveis no subsolo e queriam uma sala em um lugar alto, para corresponder à sua importância. Agora, a sala de comando fica em um dos andares mais altos da torre mais alta da usina, na sala de número 1, e os engenheiros se comunicam com o técnico por um telefone, caso detectem algum problema. Além disso, a administração da Unicamp faz o possível para deixar a empresa mais divertida, como é a tendência de grandes empresas atuais. Por isso, foram instalados escorregadores entre algumas salas. Evidentemente, só é possível ir de escorregador para uma sala que fique em uma altitude menor.
Um grave problema no reator foi detectado pelos engenheiros, mas o técnico responsável pelo reator desligou o telefone para dormir e é só questão de tempo até que o reator exploda. Os engenheiros decidiram então sair correndo, ou melhor, escorregando para tentar avisar o técnico. Além dos engenheiros, existem diversas pessoas na empresa espalhadas pelas salas. Os engenheiros vão descer pelos escorregadores a uma velocidade de 1 metro por segundo e vão gritar alertas o tempo todo. Dentro de uma mesma sala o som se propaga perfeitamente (e, podemos considerar, instantaneamente). Nos escorregadores, o grito de uma pessoa pode ser ouvido a uma distância de K metros (considere, também, instantaneamente). Note que o som pode se propagar por uma sequência de salas e escorregadores enquanto a soma total da distância nos escorregadores for menor ou igual a K metros). No entanto, como os gerentes da Unicamp não gostam de ouvir o barulho operacional da usina, há um isolamento sonoro no prédio que só permite que o som se propague de andares mais altos para andares mais baixos, e não na direção contrária. Qualquer pessoa que ouça outra pessoa gritando vai perceber o perigo e também vai começar a instantaneamente a gritar e usar os escorregadores para avisar os outros.
Você vai receber uma descrição da usina, com o número de salas, a quantidade de escorregadores e a descrição de cada escorregador. Além disso, vai receber o número de salas que contém pessoas, quais salas contém pessoas e a distância na qual as pessoas conseguem ser ouvidas nos escorregadores. A crise estará resolvida quando alguma pessoa chegar perto o suficiente do técnico para que ele ouça os gritos, acorde e desligue o reator. Sua tarefa é calcular o menor tempo necessário para que alguma pessoa avise o técnico e previna o desastre, ou indicar que isso não é possível com os escorregadores disponíveis.
Entrada
A primeira linha da entrada contém quatro inteiros N , M , C e K, respectivamente o número de salas, o número de escorregadores, o número de salas que contém pessoas e a distância na qual as pessoas conseguem ser ouvidas. As salas são identificadas por números de 1 a N . Os engenheiros sempre partem da sala de número 1 e o técnico sempre está na sala de número N . A segunda linha contém C inteiros, P 1 , P 2 , ...P C , indicando os números das salas quem contém pessoas. Cada uma das M linhas seguintes descreve um escorregador, e contém três inteiros A, B e D, indicando que existe um escorregador da sala A (mais alta) para a sala B (mais baixa), de comprimento D metros.
Saída
Seu programa deve produzir uma única linha, contendo um único número inteiro, o menor tempo possível, em segundos, para prevenir o acidente, ou −1 caso isso não seja possível.
Restrições
• Sempre há pessoas nas salas 1 e N
• 2 ≤ N ≤ 105
• 0 ≤ M ≤ 3 × 105
• 2 ≤ C ≤ 100
• 1 ≤ D ≤ 104
• 0 ≤ K ≤ 109
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
4 3 2 5 |
0 |
|
4 4 3 3 |
-1 |
|
5 7 4 7 |
7 |