Como o pessoal está tendo dificuldade com essa tarefa, estive pensando quais seriam os erros mais comuns, e seguem umas dicas:
1. O idioma inicial e final nem sempre aparecem na lista de idiomas da uma instância.
2. Evitem processamento que demora tempo quadrático no número de vértices. (Tanto na leitura, quanto na hora de procurar um caminho mínimo.) Vocês podem usar, por exemplo, uma árvore de prefixos para fazer a leitura e mapeamento dos vértices de maneira eficiente.
3. Pensem o que representa um vértice nesse problema. Dada essa representação, fica fácil encontrar um caminho mínimo no grafo.
A dica 3.1 fica para depois, caso isso não tenha ajudado em nada para a maioria das pessoas.
Sobre a dica 3, eu tentei o óbvio (obviamente errado). Coloquei cada idioma como um vértice e usei as palavras como caminhos.
Mas usando essa representação fica bem complicado usar uma busca em largura para encontrar o menor caminho.
Será que rola alguma dica agora nos minutos finais? =)
Mas usando essa representação fica bem complicado usar uma busca em largura para encontrar o menor caminho.
Será que rola alguma dica agora nos minutos finais? =)
Ishh, o PACA tem um pequeno delay para encaminhar por email as mensagens postadas aqui, e por isso não vi essa dúvida a tempo.
Uma possível maneira de representar o grafo é "multiplicar" os vértices por 26. Dessa maneira um vértice é representado por seu ID e por uma letra L, em vez de usarmos apenas o ID.
As arestas que apontam para esse vértice são, dentre as arestas que apontam para o vértice ID original, as que começam com a letra L.
As arestas que saem desse vértice são todas que saem do vértice ID original, exceto as que tem L como letra inicial.
Isso pode ser implementado fazendo uma pequena alteração do algoritmo de Dijkstra.
(Sim, o seu "óbvio" é o primeiro passo da representação, mas era necessário ir um pouco além para eliminar caminhos que tenham arestas consecutivas que comecem com a mesma letra.)
Uma possível maneira de representar o grafo é "multiplicar" os vértices por 26. Dessa maneira um vértice é representado por seu ID e por uma letra L, em vez de usarmos apenas o ID.
As arestas que apontam para esse vértice são, dentre as arestas que apontam para o vértice ID original, as que começam com a letra L.
As arestas que saem desse vértice são todas que saem do vértice ID original, exceto as que tem L como letra inicial.
Isso pode ser implementado fazendo uma pequena alteração do algoritmo de Dijkstra.
(Sim, o seu "óbvio" é o primeiro passo da representação, mas era necessário ir um pouco além para eliminar caminhos que tenham arestas consecutivas que comecem com a mesma letra.)