We present improved oracles for the distance sensitivity problem. The goal is to preprocess a graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from × to y that does not go through some failed vertex or edge f. There are two state of the art algorithms for this problem. The first produces an oracle of size Õ(n 2) that has an O(1) query time, and an Õ(mn 2) construction time. The second oracle has size O(n 2.5), but the construction time is only Õ(mn 1.5). We present two new oracles that substantially improve upon both of these results. Both oracles are constructed with randomized, Monte Carlo algorithms. For directed graphs with non-negative edge weights, we present an oracle of size Õ(n 2), which has an O(1) query time, and an Õ(n 2 √m) construction time. For unweighted graphs, we achieve a more general construction time of Õ(√n 3 · APSP + mn), where APSP is the time it takes to compute all pairs shortest paths in an aribtrary subgraph of G.