Viagem de Juquinha, algoritmos de caminho...

[Filipe Teixeira Amaral 0]

Ola, Galera to com um trabalho pra entregar aqui e tem esse problema

 

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, apresente todos os roteiros possíveis que a família de Juquinha pode fazer, 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 linhas. A primeira linha 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.

Exemplo de Entrada

9 12 1 2

2 1

1 5

4 9

3 2

9 3

3 4

4 8

4 7

7 6

5 6

4 5

3 7

Saída

 

Para cada entrada seu programa deve produzir os roteiros das cidades que podem ser alcançadas.

Exemplo de Saída

1-2-1

1-2-3

1-5-1

1-5-6

1-5-4

(esta saída corresponde ao exemplo de entrada acima)

Restrições

 

1 ≤ C ≤ 50

1 ≤ E ≤ 2500

1 ≤ L ≤ C

0 ≤ P ≤ 20

1 ≤ X ≤ C

1 ≤ Y ≤ C

 

Sei que eh possível resolver com recursividade, eu to tentando a um mês resolver e nada...

 

alguém tem alguma ideia de como resolver isso???

 

qualquer ideia será bem vinda, obrigado...

[quitZAUMMM 18]

Amigo, sugiro dar uma lidinha nesse fórum: http://br.spoj.pl/forum/

 

Eu já participei a algum tempo do site principal, acho que as repostas de lá, serão + úteis para você.

 

[]s