#78 Exercício - Estrada romana

Nome: Estrada romana
Link: http://br.spoj.pl/problems/ROMANA07/
Dificuldade: 8/10
Linguagem: C++
Tempo atingido: 0.54
Memória usada: 3.5M
Colocação alcançada: 3
Tentativas: 8

Comentário:
E pra variar, mais um exercício baseado em grafos.
Desta vez é uma árvore geradora mínima.
O que assusta um pouco nesse exercício é que os pesos de cada aresta não são dados de bandeja, porém você deve calcular cada um.
Eu demorei um pouco, mas descobri um meio de descobrir a quantidade de combinações de uma forma bem eficiente.

Dicas:
- Estudem árvore geradora mínima.
- Entendam o conceito de programação dinâmica, e tentem aplicar no modo de descobrir o peso das arestas.
- Note que a saída pode ser um pouco alta.