leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2976.cpp (1146B)

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 };