56 lines
1.7 KiB
C#
56 lines
1.7 KiB
C#
public class Solution {
|
|
private readonly int UNREACHABLE = 1_000_000_007;
|
|
private readonly int LETTERS = 26;
|
|
|
|
private void FloydWarshall(int n, int[,] distances) {
|
|
for (int k = 0; k < n; ++k) {
|
|
for (int i = 0; i < n; ++i) {
|
|
for (int j = 0; j < n; ++j) {
|
|
distances[i, j] = Math.Min(
|
|
distances[i, j],
|
|
distances[i, k] + distances[k, j]
|
|
);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
private int[,] ConstructGraph(char[] original, char[] changed, int[] costs) {
|
|
var distances = new int[LETTERS, LETTERS];
|
|
|
|
// Everything's unreachable
|
|
for (var i = LETTERS * LETTERS - 1; i >= 0; --i) {
|
|
distances[i / LETTERS, i % LETTERS] = UNREACHABLE;
|
|
}
|
|
|
|
// Go through the possible changes
|
|
for (var i = 0; i < original.length; ++i) {
|
|
var (u, v, cost) = (original[i] - 'a', changed[i] - 'a', costs[i]);
|
|
distances[u, v] = Math.Min(distances[u, v], cost);
|
|
}
|
|
|
|
// Handle self-loops
|
|
for (var i = 0; i < LETTERS; ++i) {
|
|
distances[i, i] = 0;
|
|
}
|
|
|
|
return distances;
|
|
}
|
|
|
|
public long MinimumCost(string source, string target, char[] original, char[] changed, int[] cost) {
|
|
var graph = ConstructGraph(original, changed, cost);
|
|
FloydWarshall(LETTERS, graph);
|
|
|
|
var minCost = 0;
|
|
for (int i = 0; i < source.Length; ++i) {
|
|
var operationCost = graph[source[i] - 'a', target[i] - 'a'];
|
|
if (operationCost == UNREACHABLE) {
|
|
return -1;
|
|
}
|
|
|
|
minCost += operationCost;
|
|
}
|
|
|
|
return minCost;
|
|
}
|
|
}
|