Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative
edge weights, and given an integer $k\geq 1$, we show that for some universal
constant $c$, a $(2k-1)$-approximate distance oracle for $G$ of size $O(kn^{1 +
1/k})$ can be constructed in $O(\sqrt km + kn^{1 + c/\sqrt k})$ time and can
answer queries in $O(k)$ time. We also give an oracle which is faster for
smaller $k$. Our results break the quadratic preprocessing time bound of
Baswana and Kavitha for all $k\geq 6$ and improve the $O(kmn^{1/k})$ time bound
of Thorup and Zwick except for very sparse graphs and small $k$. When $m =
\Omega(n^{1 + c/\sqrt k})$ and $k = O(1)$, our oracle is optimal w.r.t.\ both
stretch, size, preprocessing time, and query time, assuming a widely believed
girth conjecture by Erd\H{o}s.