(Enem 2010) João mora na cidade A e precisa visitar cinco clientes, localizados em cidades diferentes da sua
20. (Enem 2010) João mora na cidade A e precisa visitar cinco clientes, localizados em cidades diferentes da sua. Cada trajeto possı́vel pode ser representado por uma sequência de 7 letras. Por exemplo, o trajeto ABCDEFA, informa que ele sairá da cidade A, visitando as cidades B, C, D, E e F nesta ordem, voltando para a cidade A. Além disso, o número indicado entre as letras informa o custo do de deslocamento entre cada uma das cidades.
Como João quer economizar, ele precisa determinar qual o trajeto de menor custo para visitar os cinco clientes. Examinando a figura, percebe que precisa considerar somente parte das sequências, pois os trajetos ABCDEFA e AFEDCBA têm o mesmo custo. Ele gasta 1min 30s para examinar uma sequência e descartar sua simétrica, conforme apresentado. O tempo mı́nimo necessário para João verificar todas as sequências possı́veis no problema é de
- 60 min.
- 90 min.
- 120 min.
- 180 min.
- 360 min
Resposta: B
Resolução: