URI Online Judge | 1778

Defesa ao Grafo

Por Gustavo Stor, UFPE BR Brazil

Timelimit: 2

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?

Entrada

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 ≤ FN), 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 ≤ uN) e v (1 ≤ vN 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 ≤ KiN) 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.

Saída

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
1 0 1
0
3
1 3
1 2
1 1
9 8 1
1 2
2 3
3 4
3 5
4 7
5 6
8 4
9 5
2
6 2 3
7 4 2
9
1 15
2 2
3 9
4 14
5 11
6 50
7 20
8 15
9 15

Caso #1: 3
Caso #2: 6