  We continue the study of distance sensitivity oracles (DSOs). Given a
directed graph $G$ with $n$ vertices and edge weights in $\{1, 2, \dots, M\}$,
we want to build a data structure such that given any source vertex $u$, any
target vertex $v$, and any failure $f$ (which is either a vertex or an edge),
it outputs the length of the shortest path from $u$ to $v$ not going through
$f$. Our main result is a DSO with preprocessing time $O(n^{2.5794}M)$ and
constant query time. Previously, the best preprocessing time of DSOs for
directed graphs is $O(n^{2.7233}M)$, and even in the easier case of undirected
graphs, the best preprocessing time is $O(n^{2.6865}M)$ [Ren, ESA 2020]. One
drawback of our DSOs, though, is that it only supports distance queries but not
path queries.
  Our main technical ingredient is an algorithm that computes the inverse of a
degree-$d$ polynomial matrix (i.e. a matrix whose entries are degree-$d$
univariate polynomials) modulo $x^r$. The algorithm is adapted from [Zhou,
Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its
intermediate steps with faster rectangular matrix multiplication algorithms.
  We also show how to compute unique shortest paths in a directed graph with
edge weights in $\{1, 2, \dots, M\}$, in $O(n^{2.5286}M)$ time. This algorithm
is crucial in the preprocessing algorithm of our DSO. Our solution improves the
$O(n^{2.6865}M)$ time bound in [Ren, ESA 2020], and matches the current best
time bound for computing all-pairs shortest paths.
