Visita aos Amigos

Problema

A Livia quer visitar todos os seus amigos nas aldeias A, B, C, D e E através de transportes públicos. Ela quer visitar todos os seus amigos, sem visitar nenhum aldeia mais do que uma vez, e retorna no final da viagem a sua casa. O preço de cada viagem é indicado na imagem em baixo. Nota que o preço máximo é de três moedas.

Uma possível ordem para visitar os seus amigos que custa 11 moedas é:

Casa → B → E → A → D → C → Casa.

Pergunta

Descobre uma ordem de visita que custe o menor número de moedas possível à Livia. Se existir mais do que uma solução possível, basta que encontres uma dessas soluções.

Respostas

Escreve a ordem completando os espaços por preencher:

Casa → ___ → ___ → ___ → ___ → ___ → Casa.


Solução