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.