Palindromic changes

You are given the cost of changing $M$ pairs of lowercase characters $x$ to $y$. You are also given a string $S$.

You can change a character in string $S$ to another lowercase character by spending the cost you were given earlier. Determine the minimum cost that is required to make $S$ a palindrome.

You can assume that it is always possible to make S a palindrome.

Example:

C++

Input: 
mat
2
m t 10
a m 5
Output:
10

Approach

Java

import java.util.Arrays;

public class PalindromicChanges {
    public static void main(String args[]) {
        String str = "mat";
        int m = 2;
        long[][] cost = new long[26][26];
        long MAX = Integer.MAX_VALUE * (long) 10000;
        for (int i = 0; i < 26; i++) {
            Arrays.fill(cost[i], MAX);
        }
        char ch[][] = { { 'm', 't', 10 }, { 'a', 'm', 5 } };
        for (int i = 0; i < m; i++) {
            int x = ch[i][0] - 'a', y = ch[i][1] - 'a';
            cost[x][y] = cost[y][x] = ch[i][2];
        }
        for (int k = 0; k < 26; k++) {
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (cost[i][k] + cost[k][j] < cost[i][j])
                        cost[i][j] = cost[i][k] + cost[k][j];
                }
            }
        }
        long ans = 0;
        boolean impossible = false;
        for (int i = 0; i < str.length() / 2; i++) {
            int x = str.charAt(i) - 'a', y = str.charAt(str.length() - 1 - i) - 'a';
            if (x != y) {
                long min = Math.min(cost[x][y], cost[y][x]);
                if (min == MAX) {
                    impossible = true;
                } else {
                    ans += min;
                }
            }
        }
        System.out.print(impossible ? -1 : ans);
    }

}