Pokébolas X37265


Statement
 

pdf   zip

html

Após jogar Pokémon Go por toda a UFMA, José, primo de João e Maria e calouro de Ciência da Computação, decidiu fazer um mapa com todos os Pokéstops da cidade e as distâncias entre elas. Ele percebeu que nem sempre há um ônibus que passe entre os Pokéstops P1 e P2, mas, sempre que existir tal ônibus, este também faz o percurso de volta.

José tem um cartão de passagem Nível 4, que sempre debita o mesmo valor máximo X. Na cidade rodam ônibus com tarifas diferentes, e José está preocupado em encontrar um caminho no qual o valor máximo de tarifa entre os trechos seja o menor possível.

Input

A entrada consiste em vários casos de teste. Cada caso de teste começa com três inteiros P, T e C, que representam o número de Pokéstops, a quantidade de Trechos na cidade e as Consultas que José deve realizar.

Output

Para cada caso de teste, imprima "Caso #" com o número do respectivo caso. Na linha seguinte, para cada consulta entre P1 e P2, imprima o menor valor que seja a tarifa máxima dentre todos os caminhos entre P1 e P2.

Caso não exista um caminho entre P1 e P2, José não poderá jogar, portanto imprima "sem pokebolas".

Exemplo: No primeiro caso de teste, o menor caminho entre os pontos 1 e 5 é 1->2->3->5 (60+50+90 = 200), com valor máximo de tarifa 90. No entanto, há um outro caminho que apresenta um menor valor máximo: 1->2->3->4->5 (60+50+80+60 = 250), cujo valor máximo de tarifa é 80. Este é o menor valor máximo entre todos os caminhos possíveis.

Public test cases

  • Input

    7 6 3
1 2 60
2 3 50
3 4 80
3 5 90
4 5 60
6 7 100
1 5
3 5
1 7
0 0 0

    Output

    Caso #1
80
80
sem pokebolas

  • Input

    3 3 3
1 2 74
1 3 89
2 3 91
1 2
1 3
2 3
0 0 0

    Output

    Caso #1
74
89
89
    • Information
    Author
    Language
    English
    Official solutions
    C++
    User solutions
    C++