O enunciado do problema afirma que sempre existe uma árvore geradora (o grafo é conexo)
No entanto, fiz uns testes e tenho quase certeza de que existem casos de entrada que NÃO são conexos.
Se alguém tiver um WA misterioso, talvez seja uma boa idéia tentar encontrar a soma do custos das arvores geradoras mínimas das componentes conexas do grafo. Eu consegui passar o problema assim.
Bom, eu to levando TLE fazendo o PRIM. Fui ao fórum do exercício para ver porque acontecia isso e o povo diz que há possibilidade de ter mais de uma componente conexa nos casos testes (o que seria um erro nos casos testes). Caso meu PRIM não esteja entrando em loop em algum caso teste, acredito que tem erros na entrada.
Não ignore a possibilidade de simplesmente seu algoritmo simplesmente estar muito lerdo.
As arestas só podem ter 3 custos diferentes e esse problema deve ter sido cuidadosamente planejado para te sacanear se você ignorar esse fato. (Usando Kruskal dá pra economizar um fator log(N) por causa disso. Não tenho certeza se dá pra fazer algo parecido com o Prim também)
Uma maneira meio suja de determinar se o problema é da entrada ou lerdeza mesmo é inserir divisões por zero em uma região "proibida" do seu programa.
Por exemplo, se existir uma condição C que leva seu programa a um loop infinito, insira um if( C ) { printf("%d",1/0) ; } no meio. Se passar a dar RE ao invés de TLE, você sabe o que houve.
As arestas só podem ter 3 custos diferentes e esse problema deve ter sido cuidadosamente planejado para te sacanear se você ignorar esse fato. (Usando Kruskal dá pra economizar um fator log(N) por causa disso. Não tenho certeza se dá pra fazer algo parecido com o Prim também)
Uma maneira meio suja de determinar se o problema é da entrada ou lerdeza mesmo é inserir divisões por zero em uma região "proibida" do seu programa.
Por exemplo, se existir uma condição C que leva seu programa a um loop infinito, insira um if( C ) { printf("%d",1/0) ; } no meio. Se passar a dar RE ao invés de TLE, você sabe o que houve.
É, eu estava trabalhando com a hipótese de v^2 não ser suficiente para passar no tempo, mas como são 1000 vértices o tempo não seria o problema. Eu estou pensando mesmo que o problema está num possível looping no código, mas até agora não consegui visualizar isso. Depois tentarei passar com o código do Kruskal, que é o que a maioria do fórum do spoj fez. Mas só fiquei implicado com o TLE...
Por essa eu não esperava. Aparentemente o enunciado está errado mesmo, e o grafo dado pode ser desconexo.
Adaptem o algoritmo para que funcione da maneira sugerida pelo Hugo.
Adaptem o algoritmo para que funcione da maneira sugerida pelo Hugo.