First attempt.

Instead of doing it the 'naive' way (for each partial word, looking up
each word that matches it straight from the list, then taking the k_th
one), we first take the word list, and convert it to a dictionary
index['a'] = sorted list of (word,position) pairs, where word[0] = 'a'.
Lookup is then much faster.
First attempt.

There may be a subtlety I haven't explored:
We are given a simple connected graph, and want to find
the max. difference between
-- the distance from node[0] to node[-1]; and
-- the distance from node[0] to node[-1] where a single edge
   length is doubled.

Instead of doing a brute force, we are finding a path that achieves
the minimum distance, then computing the distance separately
for each edge on that path doubling in length... it could be the
case there are multiple paths achieving the minimal length, but
we are taking only one. Is it possible this approach misses
the key edge to double? I haven't thought about it enough.