hackercupai/hackercup huggingface dataset:
As in Chapter 1, we'll consider each possible character \(x\) (`"A"` \(\le x \le\) `"Z"`) such that all characters in \(S\) are to be changed into \(x\). The only difference is in computing the minimum number of seconds it takes to change some character \(c\) into another character \(x\) (if it's possible at all).

If we imagine an unweighted graph with \(26\) nodes (one for each letter from `"A"` to `"Z"`), such that there's a directed edge from node \(A_i\) to node \(B_i\) for each type of replacement \(i\), then the minimum number of seconds required to change \(c\) into \(x\) is equal to the shortest length of any path from node \(c\) to node \(x\) (if any such path exists).

We can precompute a \(26*26\) table of these shortest distances between all pairs of nodes by using the [Floyd–Warshall algorithm](https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm) or by performing a [BFS (breadth-first search)](https://en.wikipedia.org/wiki/Breadth-first_search) from each possible starting node, taking care to mark unreachable pairs of nodes as effectively having an infinite distance and being unusable in the final answer. For each character \(x\) and for each character \(c\) in \(S\), we can then look up the shortest distance from node \(c\) to node \(x\) in the table.

[See David Harmeyer's solution video here](https://youtu.be/p5yPTHNUTlc).