Audiophobia
Você receberá um os dados sobre um grafo e q pares de pontos. Para cada par responda qual o caminho com a menor aresta máxima entre os dois pontos.
Entrada
A entrada pode conter vários casos de teste.
A primeira linha de cada caso de teste contém três inteiros C (≤ 100), S (≤ 1000) e Q (≤ 10000), onde C indica o número de vértices (vértices são numerados usando inteiros distintos que variam de 1 a C), S representa o número de arestas e Q é o número de consultas.
Cada uma das seguintes S linhas contém três números inteiros: C1, C2 e D indicam que o peso da aresta que liga os vértices c1 e c2 () é d.
Cada uma das próximas Q linhas contém dois inteiros C1 e C2 ().
A entrada terminará com três zeros.
Saída
Para cada caso de teste i imprima: Case #i: e uma linha em branco.
Para cada consulta, se existir um caminho entre C1 e C2, imprima a resposta da pergunta acima, caso contrário imprima no path.
Imprima uma linha em branco entre dois casos de teste.
Exemplo de Entrada | Exemplo de Saída |
7 9 3 1 2 50 1 3 60 2 4 120 2 5 90 3 6 50 4 6 80 4 7 70 5 7 40 6 7 140 1 7 2 6 6 2 7 6 3 1 2 50 1 3 60 2 4 120 3 6 50 4 6 80 5 7 40 7 5 1 7 2 4 0 0 0 |
Case #1 80 60 60 Case #2 40 no path 80
|