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

CIPO - Sistema Cipoviário

Os pesquisadores do departamento de pesquisa operacional da Universidade da Columbia Britânica foram contratados para uma estranha tarefa. Vários países da África resolveram se unir e utilizar oficialmente o meio de transporte que ficou mundialmente conhecido nos filmes do Tarzan: o cipó. Há milhões de cipós na África e é surpreendente com que velocidade e eficiência uma pessoa pode se deslocar na selva utilizando esse meio de transporte. Só surgiu um pequeno problema. Os cipós são dominados por três grandes tribos: os makelelês, os malouhdás e os abedis. As tribos exigem ser pagas por cipó usado no sistema de transporte. Como eles ainda não sabem o significado de palavras como cartel, cada uma fez o seu preço, e divergiram bastante. Enquanto os makelelês exigem 1235 bongôs por cipó usado, os malouhdás exigem 8977 e os abedis 10923 (a Jane ainda está viva, e ajudou a intermediar a negociação para esta tribo).

Os pesquisadores foram contratados para escolher os cipós que comporão o primeiro sistema cipoviário do mundo. Os contratantes construíram milhões de "pontos de cipó" pela selva africana e desejam que os cipós sejam escolhidos de tal forma que seja possível ir de qualquer ponto a qualquer outro usando os cipós contratados (você pode ter de trocar de cipó algumas vezes, como fazia o Tarzan). Você deve dizer qual o custo de um sistema que atenda estes requisitos e seja o mais barato possível.

Você pode supor que existam cipós suficientes na selva para que sempre exista um sistema cipoviário que atenda os requisitos.

Entrada

A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 1000) e m (1 <= m <= 2000000), onde n é o número de "pontos de cipó" e m é o número de cipós. Cada uma das m linhas seguintes contém três inteiros u, v e c indicando que existe um cipó que vai do ponto u e até o ponto v com custo c, onde 1 <= u, v <= n e c = 1235 ou 8977 ou 10923.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima o custo de um sistema que atenda os requisitos descritos acima.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
3 3
1 2 10923
1 3 1235
2 3 1235
3 2
1 2 1235
2 3 10923

Saída:
Instancia 1
2470

Instancia 2
12158

Adicionado por:Wanderley Guimarăes
Data:2007-08-28
Tempo limite:13.02s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva para Maratona de Programação do IME - 2007

hide comments
2015-08-22 14:00:59 Alan Hahn Pereira
Olha o duplo sentido: vc vai montar uma arvore pra eles
2014-07-16 15:16:27 Vagner Kaefer [UTFPR]
É uma merda quando esses enunciados estăo incorretos! Nunca tive isso no URI, lá nem a gramática está errada, muito menos os parâmetros do problema! Pena que os professores da universidade usem essa coisa aqui! -.-
2012-08-25 17:27:39 Leandro Carlos Rodrigues [FEI]
Ok, a entrada possui grafos desconexos. Quando for este caso, a saída deve ser o valor da Floresta Geradora Mínima?
2012-05-01 21:50:46 Jeferson Lesbão de Siqueira[UNITAU]
O corretor ja foi corrigido ?
2011-08-31 16:08:34 Emílio José


Last edit: 2011-08-31 16:09:09
2011-08-29 09:08:32 Jhonatan Ríchard Raphael [UEMS]
Complementando: Vocę năo pode supor que existam cipós suficientes na selva para que sempre exista um sistema cipoviário que atenda os requisitos. Logo, a descriçăo do problema está errada! existem casos de teste no BD onde o grafo é desconexo.
2010-08-04 22:22:21 Israel [ibfs]
Vocę năo pode supor que existam cipós suficientes na selva para que sempre exista um sistema cipoviário que atenda os requisitos.
2009-12-28 21:16:43 Vinicius
testando
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.