Defesa ao Grafo
Por Gustavo Stor, UFPE 
Brazil
Por Gustavo Stor, UFPE Brazil
Tower Defense é um famoso jogo de estratégia onde o jogador deve posicionar torres de defesa para proteger algo - seja um castelo, um tesouro ou até você mesmo - contra uma horda de monstros. Há várias variações do jogo: em alguns tipos, o mapa se assemelha a um tabuleiro, e os monstros tem um caminho especifico a seguir; em outros tipos, o mapa é aberto e os monstros podem chegar ao destino final por vários meios diferentes.
Graph Defense é uma variação do Tower Defense comum. Aqui, o mapa é representado como um grafo de N vértices e M arestas. Cada vértice é uma posição em que um monstro ou uma torre (ou ambos) podem estar, em um dado momento, e as arestas representam conexões bidirecionais entre esses vértices (i.e. se há uma aresta de u para v, um monstro que está no vértice u em um dado momento pode ir para o vértice v no momento seguinte e vice-versa). O castelo, que você deseja proteger, se encontra no vértice F.
Cada torre i possui um alcance Ci, um ataque Ai e está no vértice Vi. Todos os vértices que estão a no máximo Ci arestas de distância de Vi receberão Ai de dano a cada unidade de tempo. As torres não se movem, e existem desde o início do jogo. O castelo possui um escudo mágico protetor que faz com que nenhuma torre consiga atacar o vértice F onde ele se encontra, tampouco propagar o ataque, ou seja, o vértice F é uma barreira e nada passa por ele, a não ser os monstros, possivelmente.
Cada monstro i surge durante o decorrer do jogo em um vértice Ki e possui Hi pontos de vida. Os monstros nunca ficam parados e, a cada unidade de tempo, se movem para um vértice adjacente. Eles sempre vão seguir para o destino final, o castelo, pelo caminho que causará o menor dano possível. Os monstros morrem quando alcançam 0 ou menos pontos de vida. Um monstro só consegue invadir o castelo quando chega ao destino F vivo. Se houver uma torre que alcança a posição inicial Ki do monstro, ela irá inflingir dano já no primeiro instante em que o monstro surge. Um monstro pode surgir já no castelo.
Você foi contratado para fazer uma simulação do jogo. Depois de todas as aparições de monstros, quantos conseguiram invadir o castelo ainda com vida?
A primeira linha da entrada contém T (1 ≤ T ≤ 100), o número de casos de teste. Cada caso de teste começa com três inteiros N (1 ≤ N ≤ 1000), M (0 ≤ M ≤ (N*(N-1))/2) e F (1 ≤ F ≤ N), o número de vértices, arestas e o vértice em que se encontra o castelo, respectivamente. A seguir há M linhas, cada uma com dois inteiros u (1 ≤ u ≤ N) e v (1 ≤ v ≤ N e v != u), indicando a existência de uma aresta que liga os vértices u e v. Não haverá mais de uma aresta entre um mesmo par de vértices. A seguir há um número P (0 ≤ P ≤ 100), indicando o número de torres. Cada uma das próximas P linhas conterá três inteiros Vi (1 ≤ Vi ≤ N e Vi != F), Ai (1 ≤ Ai ≤ 10⁵), e Ci (1 ≤ Ci ≤ 1000), indicando que a i-ésima torre se encontra no vértice Vi com Ai de ataque e Ci de alcance, conforme explicado na descrição do problema. Pode haver mais de uma torre no mesmo vértice, e não haverá nenhuma torre no vértice F. Por fim, haverá um inteiro Q (1 ≤ Q ≤ 10⁴), indicando o número de monstros. Cada uma das próximas Q linhas contém dois inteiros Ki (1 ≤ Ki ≤ N) e Hi (1 ≤ Hi ≤ 10⁸), indicando o vértice onde o i-ésimo monstro nasce e a quantidade de pontos de vida que ele tem no começo, respectivamente. É garantido que existe pelo menos um caminho que, não fosse pelos ataques das torres, o monstro conseguiria chegar ao castelo.
Para cada caso imprima “Caso #X: Y”, onde X é o número do caso atual, começando em 1, e Y é o número de monstros que conseguiram chegar ao castelo com vida.
| Exemplo de Entrada | Exemplo de Saída |
|
2 |
Caso #1: 3 |