Com o intuito de avaliar as condições de segurança de alguns estádios de futebol, uma comissão vai proceder à sua inspeção.
Na Tabela 4, para cada um dos sete estádios passíveis de inspeção, estão indicados o país onde o estádio se localiza e a sua capacidade.
Tabela 4 - Estádios e Capacidade
| País onde o estádio se localiza | Capacidade do estádio |
|---|---|
| África do Sul | 94 736 |
| Austrália | 83 500 |
| Coreia do Norte | 114 000 |
| Espanha | 99 354 |
| França | 81 338 |
| Inglaterra | 90 000 |
| México | 87 000 |
A comissão decidiu inspecionar apenas os estádios com capacidade superior a 85 000 espectadores.
De modo a definir um percurso, considerou a duração do voo entre os diferentes países que se apresentam na Tabela 5.
Tabela 5 - Duração dos voos entre países (formato de matriz triangular)
| Austrália | Coreia do Norte | Espanha | França | México | Inglaterra | |
|---|---|---|---|---|---|---|
| África do Sul | 14h13 | 15h57 | 10h25 | 11h22 | 18h38 | 11h46 |
| Austrália | 11h50 | 21h52 | 21h35 | 16h38 | 21h38 | |
| Coreia do Norte | 12h12 | 11h24 | 15h26 | 11h16 | ||
| Espanha | 1h32 | 12h18 | 1h55 | |||
| França | 11h56 | 5h24 | ||||
| México | 11h36 |
O percurso será definido atendendo ao método seguinte:
- escolher o menor tempo de voo, qualquer que ele seja;
- escolher, sucessivamente, os menores tempos de voo, garantindo que não são selecionados mais de dois voos que partam do mesmo país ou que cheguem ao mesmo país, e terminar depois de serem selecionados todos os países onde se localizam os estádios a inspecionar.
Apresente o percurso a efetuar pela comissão, com início na África do Sul.
Na sua resposta, apresente:
- um grafo que resulte da aplicação do algoritmo descrito;
- a ordem pela qual a comissão visitará os estádios.
Comentários
Neste momento, não há comentários para este exercício.
Para comentar, por favor inicia sessão ou cria uma conta.