leetcode

0 class Solution {

1 public:

2 long long minimumCost(const string &source, const string &target, const vector<char> &original,

3 const vector<char> &changed, const vector<int> &cost) const {

4 static unsigned long long path[26][26];

5 memset(path, 0xFF, sizeof(path));

6

7 for (int i = 0; i < size(cost); i++) {

8 auto &cpath = path[original[i] - 'a'][changed[i] - 'a'];

9 cpath = min(cpath, (unsigned long long)cost[i]);

10 }

11

12 for (int k = 0; k < 26; k++) {

13 for (int i = 0; i < 26; i++) {

14 if (path[i][k] == -1) continue;

15

16 for (int j = 0; j < 26; j++) {

17 if (path[k][j] == -1) continue;

18

19 path[i][j] = min(path[i][j], path[i][k] + path[k][j]);

20 }

21 }

22 }

23

24 long long res = 0;

25

26 for (int i = 0; i < size(source); i++) {

27 if (source[i] == target[i]) continue;

28

29 const auto cost = path[source[i] - 'a'][target[i] - 'a'];

30 if (cost == -1) return -1;

31

32 res += cost;

33 }

34

35 return res;

36 }

37 };