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.|

ROMANA07 - Estrada romana

A civilização romana dominou a Europa do século III A.C. até o século V D.C. e foi responsável por grandes construções como aquedutos, arenas esportivas e estradas. Glaubus era um construtor romano e ficou encarregado de pavimentar um conjunto de estradas já existentes, de tal forma que entre duas cidades do império sempre deve existir um caminho pavimentado entre elas, mesmo que para tal seja necessário passar por outras cidades. Glaubus dispõe de uma única equipe de construção, permitindo que somente um trecho seja pavimentado a cada instante.

Para produzir as lajes necessárias para a pavimentação foram contratadas P pedreiras e cada entrega as lajes com um determinado comprimento T em metros e a largura padrão de uma estrada romana. Duas pedreiras distintas não entregam pedras com o mesmo comprimento. Pode-se utilizar qualquer combinação de possível de pedras para formar um determinado trecho de estrada, entretanto, é proibido cortar as pedras. Por exemplo, se existem pedras de 1, 2, 3 e 4 metros, podemos pavimentar um trecho de estrada de 5 metros de seis formas distintas: 5 pedras de comprimento 1; 1 pedra de comprimento 1 e duas de comprimento 2; 1 pedra de comprimento 1 e uma de comprimento 4 ; 3 pedras de comprimento 1 e uma de comprimento 2; 2 pedras de comprimento 1 e uma de comprimento 3; e uma pedra de comprimento 2 e uma de comprimento 3. Nenhuma outra combinação além dessas seis é possível para o trecho de 5 metros com essas pedras.

Note que, no exemplo anterior, se retirarmos as pedras de comprimento 1, passamos a ter somente uma combinação para o trecho de 5 metros: uma pedra de comprimento 2 e uma pedra de comprimento 3. Além disso, nesse caso não é mais possível pavimentar um trecho de comprimento 1.

Os conselheiros do império notaram que o tempo de pavimentação de cada trecho é proporcional ao número de combinações possíveis de pedras para se pavimentar esse trecho, exceto se houver zero combinações possíveis, pois nesse caso o trecho não pode ser pavimentado. Glaubus então deseja pavimentar o conjunto de estradas que ligue todas as cidades e cujo tempo total de pavimentação seja o menor possível, supondo que os trechos sejam pavimentados em sequência, um imediatamente após o outro. Como Glaubus vive no sec. II D.C mas possui poderes místicos, ele entrou em contato com você no futuro e pediu sua ajuda.

Tarefa

Escreva um programa que, dado o número de cidades romanas, o número de pedreiras, os possíveis trechos a serem pavimentados e suas distâncias, determine o menor tempo possível para se pavimentar os trechos que ligam as cidades romanas.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém três inteiros N, P e E que representam o número de cidades, o número de pedreiras e o número de possíveis trechos a serem pavimentados respectivamente (2 ≤ N ≤ 250, 1 ≤ P ≤ 20, 1 ≤ E ≤ ½N2). As cidades são numeradas de 1 a N. A linha seguinte contém P inteiros em ordem crescente, indicando o comprimento das pedras produzidas pelas P pedreiras contratadas. Nenhuma pedra tem comprimento maior que 100. As E linhas seguintes contém três inteiros cada, U, V e T indicando que um trecho de comprimento T (1 ≤ T ≤ 100) ligando a cidade U à cidade V pode ser pavimentado. O tempo total nunca é maior que 2 bilhões.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo o menor tempo possível para se pavimentar os trechos de estrada necessários ou −1 caso não seja possível pavimentá-las de acordo com as restrições acima.

Exemplo

Entrada:
3 4 2
1 2 3 4
1 2 10
2 3 5

Saída:
29

Entrada:
4 3 6
2 5 10
1 2 1
1 3 3
1 4 20
2 3 10
2 4 3
3 4 2

Saída:
10

Entrada:
5 2 7
13 19
1 2 12
2 3 15
3 4 8
3 5 14
1 4 3
1 5 19
4 5 13

Saída:
-1


Adicionado por:Wanderley Guimarăes
Data:2012-07-21
Tempo limite:0.100s
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:Seletiva IOI 2007

hide comments
2012-09-22 20:36:25 Gabriel Luís Mello Dalalio [ITA]
Os casos com overflow foram retirados. Todas as submissőes foram rejulgadas.
2012-09-16 16:16:19 Diogo [ITA]
Ao resolver o problema utilizando int, recebi resposta correta. Ao utilizar long long int, recebi resposta errada. Realizando alguns testes, percebi que a resposta de alguns casos testes năo está cabendo em um int, um overflow está ocorrendo e a resposta aceita considera o overflow. Sugiro a retirada dos casos testes em que a resposta năo cabe em um int.
2012-07-21 20:15:04 Gabriel Luís Mello Dalalio [ITA]
Obrigado Luciano, o enunciado foi corrigido, faltava a combinaçăo de 1 pedra de comprimento 1 e uma de comprimento 4
2012-07-21 17:14:45 Luciano G. Sampaio [FATEC - SO]
Năo está errada esta parte???

"...se existem pedras de 1, 2, 3 e 4 metros, podemos pavimentar um trecho de estrada de 5 metros de seis formas distintas:
5 pedras de comprimento 1;
1 pedra de comprimento 1 e duas de comprimento 2;
3 pedras de comprimento 1 e uma de comprimento 2;
2 pedras de comprimento 1 e uma de comprimento 3;
e uma pedra de comprimento 2 e uma de comprimento 3.
Nenhuma outra combinaçăo além dessas duas é possível para o trecho de 5 metros com essas pedras."

Năo seria cinco formas distintas? Ou esta faltando uma?
E no final ao invés de 'além dessas duas' năo seria 'além dessas cinco'? ou 'além dessas seis' se estiver faltando uma
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.