Когда я увидел эту задачу, то мне сразу пришло решение с MinCost-MaxFlow алгоритмом. Возможно есть и проще, но этот разбор использует именно идею минимального по весу максимального паросочетания.

Давайте подсчитаем, сколько каких букв в первой и во второй строке. Создадим сеть, где кроме стока и исктока будут две доли вершин - для первой строки и второй. Проведем пропускную способность из истока к буквам первой доли такую, сколько раз эта буква встречается в нашей первой строке. Аналогично по второй строке проведем ребра из второй доли к стоку. Цена таких ребер равна нулю.

Далее будем делать ребра из первой доли во вторую, неограниченные пропускной способностью для ребер, которые нам даны во входных данных(других просто нет). Цена таких ребер берется из входных данных, но тут есть одно "но". Возможно выгодно для получения буквы "Б" из буквы "А", предворительно обменять ее на букву "В". Поэтому флойд по ценам в начале не помешает. И таким образом у нас получится матрица расстояний из которой надо перенести все ребра у которых цена не бесконечность в сеть, между первой и второй долей. Не забудьте, что g[i][i] = 0;

Когда мы построили сеть, найдем Макс.Поток-Мин.Строимости в сети. Если поток не равен длине второй строки, то ответ "Impossible". Иначе выводим стоимость.

Время рабты алгоритма: время работы алгоритма нахождения потока минимальной стоимости + время Флоида. При реализации потока ФордБеллманом выйдет что-то типа $O(n^2m^2 + n^3)$, а n у нас порядка 26*2, ребер (26*2)^2. Но это оценка сверху и все прекрасно проходит.