# Untitled

unknown
plain_text
15 days ago
1.8 kB
0
Indexable
Never
```class Solution {
public:
long long minimumCost(string source, string target, vector<char>& original, vector<char>& changed, vector<int>& cost) {
long long ans = 0;
vector<vector<pair<int, int>>> G;
vector<vector<long long>> D;
G.assign(27, {});
D.assign(27, {});
for (int i=0; i<original.size(); ++i) {
G[original[i] - 'a'].emplace_back(pair{changed[i] - 'a', cost[i]});
}
for (int i=0; i<original.size(); ++i) {
if (D[original[i] - 'a'].size() != 0) continue;
if (G[original[i] - 'a'].size() == 0) continue;
else D[original[i] - 'a'] = dijkstra(G, original[i] - 'a');
}
for (int i=0; i<source.length(); ++i) {
int s = source[i] - 'a';
int t = target[i] - 'a';
if (s == t) continue;
vector<long long> d = D[s];
if (d.size() == 0) return -1;
if (d[t] == INT_MAX) return -1;
else ans += d[t];
}
return ans;
}

vector<long long> dijkstra(const vector<vector<pair<int, int>>> &G, int s) {
vector<long long> d(27, INT_MAX);
vector<bool> visited(27, false);
using QueuePair = pair<long long, int>;
priority_queue<QueuePair, vector<QueuePair>, greater<QueuePair>> Q;
d[s] = 0;
Q.emplace(d[s], s);
while (!Q.empty()) {
int u = Q.top().second;
Q.pop();
if (visited[u]) continue;
visited[u] = true;
for (auto [v, cost] : G[u]) {
if (d[v] > d[u] + cost) {
d[v] = d[u] + cost;
Q.emplace(d[v], v);
}
}
}
return d;
}
};```