• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

mogers

[Exercicio] Old West Rumours (grafos)

2 mensagens neste tópico

Boas

A secção tem estado muito parada  ;)

Tive a tentar resolver este exercício Old West Rumours 

Mas não encontrei solução melhor do que a trivial (ou pouco melhor do que a trivial :))

Alguém consegue resolver isto eficientemente?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um BFS não resolve o problema?

Tens poucos estados, só mesmo a posição do Billy e o tempo actual.

Suponho que seja possível ele chegar lá e escolher não parar o rumor, logo, em cada posição, ele tem dois tipos de alternativas: ou parte para uma das cidades adjacentes, e gasta o tempo da viajem, ou mantem-se na mesma cidade, gasta o tempo para parar o rumor e aumenta o numero de rumores parados por 1.

Tens no máximo 50towns e 200*50 em tempo, o que é perfeitamente possível de resolver.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora