Skip to main content
2 de 2
adicionou 43 caracteres ao conteúdo
tayllan
  • 2,5mil
  • 15
  • 19

A primeira coisa que você deve perceber no problema é que o custo entre as diversas linhas de ônibus é sempre 1, então você não precisa nem mesmo utilizar o algoritmo de Dijkstra ou qualquer outro algoritmo de caminho mais curto genérico. Uma simples Busca em Largura é o suficiente e mais rápida.

O segundo ponto importante é como construir seu grafo. Pelo enunciado do problema você consegue perceber que um Câmpus é ligado à X outros campi por uma linha de ônibus, a qual você pode utilizar por tempo indefinido (desde que não saia da linha) para andar entre todos os campi conectados por tal linha. O que isso lhe diz é: todos os vértices (os campi) de uma linha de ônibus têm acesso a todos os outros vértices, ou seja, são conectados no grafo, com arestas de peso 1.

Pegando a entrada de exemplo do problema:

9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8

Na segunda linha temos 2 3 4 6 7 9 (podemos ignorar o 6 aqui, pois ele só é utilizado para informar quantos vértices estão presentes na linha). Todos esses vértices apresentados podem chegar a qualquer um dos outros vértices pagando apenas um preço de 1, então a representação dessas conexões em uma matriz de adjacência fica da seguinte forma:

   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
    --- --- --- --- --- --- --- --- ---
 1 |   |   |   |   |   |   |   |   |   |

 2 |   |   | T | T |   | T | T |   | T |

 3 |   | T |   | T |   | T | T |   | T |

 4 |   | T | T |   |   | T | T |   | T |

 5 |   |   |   |   |   |   |   |   |   |

 6 |   | T | T | T |   |   | T |   | T |

 7 |   | T | T | T |   | T |   |   | T |

 8 |   |   |   |   |   |   |   |   |   |

 9 |   | T | T | T |   | T | T |   |   |

onde T indica que há uma aresta conectando dois vértices, e a ausência de T indica que não é possível chegar de um vértice a outro (esse grafo representa apenas as conexões dadas pela primeira linha de ônibus do exemplo!).

Resumindo: na hora de ler a entrada do problema, construa seu grafo de forma que todos os Campi de uma linha tenham acesso a todos os outros Campi da mesma linha. E execute uma Busca em Largura sobre o grafo. Isso lhe dará a resposta correta.

tayllan
  • 2,5mil
  • 15
  • 19