Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PAISES - Países em guerra

No ano 2050, após diversas tentativas da ONU de manter a paz no mundo, explode a terceira guerra mundial. Segredos industriais, comerciais e militares obrigaram todos os países a utilizar serviços de espionagem extremamente sofisticados, de forma que em cada cidade do mundo há ao menos um espião de cada país. Esses espiões precisam se comunicar com outros espiões, com informantes e mesmo com as suas centrais durante as suas ações. Infelizmente não existe uma forma segura de um espião se comunicar em um período de guerra, então as mensagens são sempre enviadas em código para que somente o destinatário consiga ler a mensagem e entender o seu significado.

Os espiões utilizam o unico serviço que funciona no período de guerra, os correios. Cada cidade possui uma agência postal onde as cartas são enviadas. As cartas podem ser enviadas diretamente ao seu destino ou a outras agências postais, até que a carta chegue à agência postal da cidade de destino, se isso for possível.

Uma agência postal na cidade A pode enviar diretamente uma carta impressa para a agênciae postal da cidade B se houver um acordo de envio de cartas, que determina o tempo, em horas, que uma carta leva para chegar da cidade A à cidade B (e não necessariamente o contrário).a Se não houver um acordo entre as agências A e B, a agência A pode tentar enviar a carta a quantas agências for necessário para que a carta chegue ao seu destino, se isso for possível.

Algumas agências são interligadas por meios eletrônicos de comunicação, como satélites e fibras ópticas. Antes da guerra, essas ligações atingiam todas as agências, fazendo com que uma carta fosse enviada de forma instantânea, mas durante o período de hostilidades cada país passou a controlar a comunicação eletrônica e uma agência somente pode enviar uma carta a outra agência por meio eletrônico (ou seja, instantaneamente) se ela estiver no mesmo país. Duas agências, A e B, estão no mesmo país se houver uma forma de uma carta impressa enviada de uma das agências ser entregue na outra agência.

O serviço de espionagem do seu país conseguiu obter o conteúdo de todos os acordos de envios de mensagens existentes no mundo e deseja descobrir o tempo mínimo para se enviar uma carta entre diversos pares de cidades. Você seria capaz de ajudá-lo?

Entrada

A entrada contém vários casos de teste. A primeira linha de cada caso de teste contém dois inteiros separados por um espaço, N (1 ≤ N ≤ 500) e E (0 ≤ E ≤ N2), indicando o número de cidades (numeradas de 1 a N) e de acordos de envio de mensagens, respectivamente. Seguem-se, então, E linhas, cada uma com três inteiros separados por espaços, X, Y e H (1 ≤ X, Y ≤ N, 1 ≤ H ≤ 1000), indicando que existe um acordo para enviar uma carta impressa da cidade X à cidade Y , e que tal carta será entregue em H horas.

Em seguida, haverá uma linha com um inteiro K (0 ≤ K ≤ 100), o número de consultas. Finalmente, virão K linhas, cada uma representando uma consulta e contendo dois inteiros separados por um espaço, O e D (1 ≤ O, D ≤ N). Você deve determinar o tempo mínimo para se enviar uma carta da cidade O à cidade D.

Saída

Para cada caso de teste da entrada seu programa deve produzir K linhas na saída. A I-ésima linha deve conter um inteiro M , o tempo mínimo, em horas, para se enviar uma carta na I-ésima consulta. Se não houver meio de comunicação entre as cidades da consulta, você deve imprimir ”Nao e possivel entregar a carta”(sem acentos).

Imprima uma linha em branco após cada caso de teste.

Exemplo de entrada

 

4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
5
1 2
1 3
1 4
4 3
4 1
3 3
1 2 10
2 3 1
3 2 1
3
1 3
3 1
3 2
0 0

Saída para o exemplo de entrada

 

0
6
6
0
Nao e possivel entregar a carta

10
Nao e possivel entregar a carta
0

Adicionado por:Wanderley Guimarăes
Data:2009-09-30
Tempo limite:0.317s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Primeira fase da Maratona de Programação - 2006

hide comments
2017-03-05 18:00:17
Façam no URI, recebi TLE mesmo com AC no URI, os limites estão errados.
2015-11-27 14:05:49 Fernando Marcos Souza Silva
Uma dica é pensar em componentes fortemente conectados (SCC) e consultas de alcançabilidade usando estes componentes...

Cidades de um mesmo país formam um SCC...
2015-07-03 19:48:05 Elsio [UFABC]
Uma forma de provar que esse problema NÃO aceita o cin é submeter o esqueleto, pegando todas as variáveis usando o cin, sem fazer nenhum processamento. Esperaria-se receber "resposta errada" mas o que retorna é limite de tempo.

Outra prova é que o meu, feito com Floyd, que é O de N ao cubo passou com 0.30s e o feito com dijkstra atingiu o limite, mas passou com 0.12s quando eu troquei o cin por scanf.
2015-07-03 07:28:34 Elsio [UFABC]
Mais um daqueles problemas em que usar o scanf (ao invés do cin) é necessário :p
Já é o segundo que eu vejo no spoj que a mesmíssima lógica, o mesmíssimo código, não passa com cin mas passa com scanf ¬¬
2014-07-27 08:10:51 Vagner Kaefer [UTFPR]


Last edit: 2014-07-27 08:11:13
2014-05-05 00:07:04 William XYZ [FAJ]
vocęs devem năo ter notado que quando 2 cidades possuem acordo entre si, esta transiçăo tem custo 0 horas. -.-
2014-01-16 16:35:21 Luciano Ribeiro
os exemplos estao corretos sim
2013-09-16 21:36:02 Andrei [FATEC-BS]
Segue a saída que eu acredito ser a correta para esse conjunto de entrada:

5
11
19
7
Nao e possivel entregar a carta

11
Nao e possivel entregar a carta
1
2012-08-19 01:51:09 João Dias
Implementei um algoritmo que dá as respostas corretas tanto para os exemplos tanto para outros casos de teste que elaborei, mesmo assim quando submeto dá resposta errada. Alguém tem alguma dica, ou sabe de uma situaçăo que devo testar?
2011-08-25 03:38:43 leal
preste atençăo no que diz o problema...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.