Submit | All submissions | Best solutions | Back to list |
POUPT21 - Pedágio |
Como prêmio pela primeira colocação na Olimpíada Brasileira de Informática, Juquinha e sua família ganharam uma viagem de uma semana à Coréia do Sul. Como o país é deslumbrante, com tradições, cultura, arquitetura e culinária muito diferentes das do Brasil, o pai de Juquinha, o Sr. Juca, decidiu alugar um carro para conhecer melhor o país. As estradas são muito bem cuidadas; todas são de sentido duplo, e duas cidades podem ser ligadas diretamente por mais de uma estrada. No entanto, em todas as estradas paga-se um pedágio de valor fixo (há um pedágio em cada direção, entre duas cidades). Como o Sr. Juca não tem muito dinheiro para gastar, as viagens com o carro devem ser muito bem planejadas.
Tarefa
Escreva um programa que, conhecidas as cidades e estradas existentes no país, e a cidade onde Juquinha e sua família estão, encontre cada cidade (que não a cidade onde eles estão) que possa ser visitada por eles, dada a restrição de que o Sr. Juca deseja pagar no máximo P pedágios (considerando apenas a viagem de ida).
Entrada
A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém quatro números inteiros C, E, L e P. Os valores C e E indicam respectivamente o número de cidades e o número de estradas existentes. As cidades são identificadas por inteiros de 1 a C. os valores L e P indicam, respectivamente, a cidade onde a família de Juquinha está no momento e o número máximo de pedágios que o Sr. Juca está disposto a pagar. As E linhas seguintes contêm cada uma a informação de uma estrada, representada por um par de números inteiros positivos X e Y, indicando que há uma estrada (de sentido duplo) da cidade X para a cidade Y. O final da entrada é indicado por C = E = L = P = 0.
Saída
Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado a partir de 1. Na segunda linha devem aparecer os identificadores das cidades que podem ser alcançadas, em ordem crescente, separados por pelo menos um espaço em branco. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.
Exemplo
Entrada: 5 4 2 1 1 2 2 3 3 4 4 5 9 12 1 2 2 1 1 5 2 1 3 2 9 3 3 4 4 8 4 7 7 6 5 6 4 5 3 7 0 0 0 0 Output: Teste 1 1 3 Teste 2 2 3 4 5 6
Restrições
0 <= C <= 50 (C = 0 apenas para indicar o fim da entrada)
0 <= E <= 2500 (E = 0 apenas para indicar o fim da entrada)
0 <= L <= C (L = 0 apenas para indicar o fim da entrada)
0 <= P <= C (P = 0 apenas para indicar o fim da entrada)
1 <= X <= C
1 <= Y <= C
Added by: | IFTM_Maratona |
Date: | 2023-05-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C |
Resource: | OBI |