Aunque el código de dijsktra haya alcanzado la complejidad requerida, lo veo aún algo ineficiente por el bucle de las líneas 56 a 60. Este blucle sobreescribe el valor de suma en cada iteración, sobreviviendo solamente el último calculado. Para mejorarlo, propongo eliminar la línea 59 y hacer el cálculo de suma en la línea 63, es decir, copiar las líneas 55, 56 y 59 al hueco de la 63. No debería variar la complejidad computacional pero sí mejorar la eficiencia.

Otra idea sería calcular las potencias de los dígitos no por multiplicación reiterada, alcanzando O(log N), sino por cuadrados sucesivos (cf. Exponentiation by squaring), lo que nos debería llevar a O(log log N), aunque quizás con datos int no podamos llegar a observar la diferencia.

EDIT: La complejidad O(log log N) se alcanzaría sólo para las potencias de los dígitos calculadas después de su frecuencia. El cálculo de estas frecuencias sigue siendo O(log N) y seguiría dominando la complejidad, aunque con este método reduciríamos el código a ejecutar O(log N) veces.

Hola, podías explicar mejor lo que pretendes con "pasar a archivos", pero observando el segundo código veo que pasas un puntero a fichero que no usas en funciones auxiliares. Sigues utilizando los scanf/printf de consola cuando quizás preferirías usar fscanf y fprintf con ese puntero a fichero. Eso depende de lo que quieras conseguir.