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.)
Forum