Solução de João Guilherme
Para ver o problema original, clique aqui.
Esse problema é uma simples modificação do algoritmo de Floyd-Warshall (uma solução usando Djikstra também é possível, e ambas estão contidas no código). Primeiro notamos que a complexidade do algoritmo passa bem no tempo da questão, segundo vemos como o algoritmo funciona, ele pega o melhor caminho do vértice i ao j usando apenas vértices no conjunto {1, 2, …, k} para cada k de 1 a n. No nosso caso nós definimos o melhor caminho como sendo o que tem a maior aresta mínima, assim em vez de tomar o mínimo entre o caminho que temos de i a j e o caminho de i a k + o caminho de k a j, tomamos o máximo entre o caminho de i a j e o peso mínimo entre as arestas no caminho de i a k e de k a j. Por fim imprimimos a distância entre as duas cidades desejadas.
Segue código para melhor entendimento.
https://gist.github.com/jogu99/74aacbdce49b2b83a37e
Deixe um comentário