Question

Passagens: O quadro abaixo mostra o preço em reais das passagens para viagens entre duas das cidades A, B, C, D e E. Note que o preço de ida e o preço de volta entre duas das mesmas cidades podem ser diferentes. Fernando quer sair de uma dessas cidades e visitar todas as demais, gastando o mínimo possível. Quanto Fernando irá gastar?

Answer 1

Resposta:

O custo mínimo será de 5.

Explicação passo-a-passo:

Como são 5 cidades, Fernando terá de fazer 4 viagens para passar por A, B, C, D e E. Usando apenas viagens de custo 1, não conseguiremos atingir todas as cidades, pois de A pode-se chegar em C, que por sua vez leva a E, mas B e D ficariam isoladas. Em outras palavras, não existe conexão ao valor 1 do grupo {A,C,E} para o grupo {B,D} ou vice-versa, o que impossibilita uma viagem de custo total 4. Assim, o custo mínimo será 5, que pode ser obtido através das viagens ACEBD.