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

RMAPA11 - Reduzindo detalhes em um mapa

 

Leonardo Nascimento é um garoto de 13 anos apaixonado por cartografia. Durante as férias de janeiro de 2011, ele alternava seu tempo entre navegar na internet (pesquisando sobre mapas) e arrumar sua coleção de mapas. Navegando na internet, Leonardo descobriu um site especializado em mapas, o Google Maps. Depois de alguns dias usando o site, Leonardo percebeu que quando diminuía o zoom algumas ruas não eram mais exibidas no mapa, isto é, o zoom determinava também o nível de detalhe do mapa. A figura abaixo ilustra um dos testes feito por Leonardo.

Ele sabe que você participa da OBI e que você adora resolver os problemas que envolvem mapas. Então resolveu formular o seguinte problema: dado um mapa de cidades e rodovias que as ligam, selecione um subconjunto das rodovias tal que entre qualquer par de cidades exista uma rota ligando-as e a soma dos comprimentos das rodovias é mínimo. Na figura abaixo e à esquerda temos um exemplo com cinco cidades e seis rodovias ligando-as. A figura abaixo e à direita ilustra uma solução cuja soma dos comprimentos é 34.

Para facilitar um pouco sua vida, Leonardo determinou que você só precisa dizer a soma dos comprimentos das rodovias do subconjunto selecionado para um dado mapa.

Entrada

A primeira linha da entrada contém dois números N e M que representam o número de cidades e o número de rodovias respectivamente. Cada uma das próximas M linhas é composta por três inteiros U, V e C que indiciam que existe uma rodovia de comprimento C que liga as cidades U e V.

Saída

A saída consiste em apenas uma linha contendo a soma do comprimento das rodovias selecionadas.

Restrições

  • 1 ≤ N ≤ 500.
  • 1 ≤ M ≤ 124750.
  • 1 ≤ U, VN e U ≠ V .
  • 1 ≤ C ≤ 500.

Exemplos

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

Saída
34

Entrada
4 6
1 2 1
1 3 10
1 4 1
2 3 1
2 4 10
3 4 1

Saída
3


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
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:OBI 2011 - fase 2 nível 2

hide comments
2018-05-28 04:10:26 Elsio [UFABC]
Ok, consegui com prim, lista de adj e pypy 2.6 ao invés do 2.7
2018-05-28 03:18:50 Elsio [UFABC]
Prim passa em C++ mas não passa em Python
2016-04-17 18:27:53 Elsio [UFABC]
Tipo o Rede otica: br.spoj.com/problems/REDOTICA/
esse eu resolvi com PRIM. o outro com Kruskal
2016-01-24 17:57:49
Raphael Medeiros, o meu passou com kruskal
2015-03-08 04:20:14 Raphael Medeiros
Algorítimo de Kruskal passando com 100 pontos no site da OBI e aqui TLE...
2013-03-06 19:19:05 luccasiau
O meu passou de boa com Prim.
2012-11-28 01:19:50 Alan Paiva
Porqe nao passa com prim?
2012-07-27 22:55:47 Guilherme Lopes [FATEC-SO]
N^3 năo passa

Last edit: 2013-07-28 21:13:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.