Descrição
Um bom general de guerra deve tomar decisões rápidas, e ao mesmo tempo ser um bom estrategista. Uma das funções do general é delegar soldados a diversos pontos estratégicos, de modo que o inimigo seja supreendido e derrotado. Há diversos pontos estratégicos no campo de batalha, assim como diversas rotas que interligam esses pontos.
O seu campo está, porém, sendo bombardeado, e essas rotas não são tão seguras mais. Uma vez que uma bomba caia em uma rota, tal terreno se torna irregular e a sua travessia se torna impossível. Para contornar tal problema, o general delegou uma nova tarefa a alguns soldados: encontrar novas rotas.
O general pediu sua ajuda então para calcular qual o caminho mais curto entre a base da operação e os pontos estratégicos. Você será informado sobre o estado inicial do campo de batalha, com N pontos estratégicos (sendo o ponto 1 a base da operação) e M rotas. Conforme as bombas inutilizam algumas rotas, e outras rotas vão sendo encontradas pelos soldados, você deve atualizar seu cálculo para que o general possa fazer bom uso de tais informações.
Boa sorte, o país depende de você.
Entrada
A entrada contém diversos casos de teste. Cada caso de teste inicia com dois inteiros, N e M (2 ≤ N ≤ 300 e 1 ≤ M ≤ 1000), representando, respectivamente, o número de pontos estratégicos e o número de rotas que interligam dois pontos estratégicos. Após, haverão M linhas, cada uma com três inteiros U, V e W (1 ≤ U, V ≤ N e 1 ≤ W ≤ 100) cada, representando que há uma rota que interliga o ponto U ao ponto V, em direção única, com distância W.
Haverá então um inteiro Q (1 ≤ Q ≤ 500), que representa o número de consultas ou atualizações que serão feitas sobre essas rotas. Nas próximas Q linhas haverá uma letra e um determinado número de inteiros.
Se a letra digitada for a letra R, haverá em seguida dois inteiros U e V (1 ≤ U, V ≤ N), indicando que a rota que antes interligava o ponto U até o ponto V foi bombardeada.
Caso a letra digitada for a letra I, haverá em seguida três inteiros U, V e W (1 ≤ U, V ≤ N e 1 ≤ W ≤ 100), indicando que foi encontrada uma nova rota que interliga o ponto U até o ponto V, com distância W.
E caso a letra digitada for a letra P, haverá em seguida um inteiro V (1 ≤ V ≤ N), e você deve informar ao general qual a distância mínima entre a base da operação e o ponto estratégico V.
A entrada termina quando N = M = 0.
Saída
Para cada caso de teste haverá um número não definido de linhas de saída. Sempre que, na entrada, o general requisitar a distância mínima entre a base da operação e um ponto estratégico (letra P), tal distância deve ser impressa em uma linha única. Caso não seja possível chegar a tal ponto estratégico, deve-se imprimir -1. Deve haver uma linha em branco após cada caso de teste.
| Exemplos de Entrada | Exemplos de Saída |
|---|---|
|
3 3 |
4 |
Efetue Login ou Cadastre-se para submeter uma solução.
Criado por Cristhian Bonilha | Adaptado por erich.rodriguesf |