Guardar todas as arestas e seus custos é simplesmente uma forma diferente de representar o grafo.
Se você conseguir o problema sem usar uma matriz ou lista de adjacência, só guardando as arestas, não tem problema.
Forum