Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PEDAGIO - 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


Adicionado por:Wanderley Guimarăes
Data:2006-04-21
Tempo limite:0.155s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2002

hide comments
2016-09-12 05:50:20
Testei com grafo desconexo e funcionou, mesmo assim meu código está sendo rejeitado.
2015-03-17 14:53:00 Wesley Kanashiro [UFMS]
O grafo pode ser conexo ou năo . . .
2014-05-17 03:54:17 Vagner Kaefer [UTFPR]
Busca em largura......

Last edit: 2014-06-27 16:00:03
2013-12-21 16:53:07 Z


Last edit: 2013-12-21 18:50:19
2012-06-05 01:08:23 Léo BH
Estava levando NZEC ao submeter a soluçăo. Acrescentei um "trim()" na leitura das estradas e resolveu o problema. Fica a dica para quem tentar resolver esse problema também.
2009-04-27 19:48:35 opa!
como voces estao fazendo as estradas?
com while() dentro do mais e a condição de parada ou somente o main para 1 caso?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.