Caminho mais largo
Será dado um grafo ponderado e duas cidades, pede-se o caminho com a maior aresta mínima entre essas duas cidades.
Entrada
A entrada irá conter um ou mais casos de teste. A primeira linha de cada caso de teste conterá dois inteiros: o número de vértices n ( ) e o número de arestas r () que compõem o grafo.
Em seguida, R linhas seguirão, cada um descrevendo uma aresta, nomeando os dois vértices ligados por esta e dando o peso da aresta. Os nomes dos vértices não terão mais de 30 caracteres e não contêm espaço em branco. Os pesos são inteiros no intervalo de 0 - 10000. As arestas são bidirecionais.
A última linha do caso de teste contém dois nomes de vértices: início e destino.
Entrada será terminada por dois valores de 0 para n e r.
Saída
Para cada caso de teste, imprima três linhas:
Uma linha dizendo "Scenario #x ", onde x é o número do caso de teste.
Uma linha dizendo "y ", onde y é a menor aresta do caminho encontrado.
Uma linha em branco.
Exemplo de Entrada | Exemplo de Saída |
4 3 Fortaleza Eusebio 100 Eusebio Juazeiro 80 Juazeiro Mumbaba 120 Fortaleza Mumbaba 5 5 Karl Stut 100 Stut Ulm 80 Ulm Muen 120 Karl Ham 220 Ham Muen 170 Muen Karl 0 0 |
Scenario #1 80 Scenario #2 170 |