Intermediário Informática - Semana 23

0 Flares Facebook 0 0 Flares ×

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 (c_{1} \neq c_{2}) é d.
Cada uma das próximas Q linhas contém dois inteiros C1 e C2 (C_1 \neq C_2).

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

 

 

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: