Алгоритм Дейкстры на графе

Есть задача по информатике
«Гуляющий кубик»
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на один тест.
Гарри Поттеру на день рождения подарили волшебный кубик. Кубик находится на
некоторой клетке обычной шахматной доски размером 8×8. Кубик полностью закрывает
собой ровно одну клетку доски, т.е. размер ребра кубика равен размеру стороны клетки
доски. На каждой стороне кубика записано какое-то целое число N (0 ≤ N ≤ 1000). На
разных сторонах кубика могут быть различные числа.
Из начальной клетки кубик с помощью заклинания перемещается по доске путем его
поворота через соответствующее ребро на соседнюю клетку. Каждому возможному пути
перемещения кубика из начальной клетки в конечную можно поставить в соответствие
сумму чисел, побывавших на его нижней грани, при этом каждое число добавляется
столько раз, сколько оно появлялось на нижней грани кубика. Числа, соответствующие
начальному и конечному положению кубика, также суммируются. Путь кубика считается
оптимальным, если при достижении конечной клетки названная сумма оказывается
минимальной.
Требуется написать программу, определяющую путь между двумя заданными клетками,
которому будет соответствовать минимальная сумма чисел, побывавших на нижней грани
кубика. Начальная и конечная клетки различны.
Формат входных данных:
Во входном файле INPUT.TXT в первой строке через пробел записаны координаты
начальной и конечной клеток в следующем формате: первый символ – буква от ‘a’ до ‘h’
включительно, определяющая номер столбца на шахматной доске, второй – цифра от 1 до
8 включительно, определяющая номер строки.
Во второй строке файла находятся 6 чисел, которые записаны на гранях кубика
спереди, сзади, сверху, справа, снизу и слева соответственно. Числа в строке разделены
пробелами.
Формат выходных данных:
Выходной файл OUTPUT.TXT состоит из двух строк. В первой строке записана
минимальная сумма чисел пути. Во второй строке выведен сам оптимальный путь
перемещения кубика или один из возможных путей, если их несколько. Путь представляет
собой последовательность координат клеток на шахматной доске, отображающих процесс
перемещения кубика. Он начинается в начальной клетке и заканчивается в конечной. Все
координаты клеток должны быть представлены в том же формате, что и во входном файле
и разделены пробелами.
Пример файлов входных и выходных данных:

OUTPUT.TXT	INPUT.TXT
е2 e3	5
0 8 1 2 1 1	e2 d2 d1 e1 e2 e3

Искал в интернете там только про уже готовое поле и изменять каждое число очень сложно. Подскажите пожалуйста.

0