  We consider first-passage percolation on the class of "high-dimensional"
graphs that can be written as an iterated Cartesian product $G\square G \square
\dots \square G$ of some base graph $G$ as the number of factors tends to
infinity. We propose a natural asymptotic lower bound on the first-passage time
between $(v, v, \dots, v)$ and $(w, w, \dots, w)$ as $n$, the number of
factors, tends to infinity, which we call the critical time $t^*_G(v, w)$. Our
main result characterizes when this lower bound is sharp as
$n\rightarrow\infty$. As a corollary, we are able to determine the limit of the
so-called diagonal time-constant in $\mathbb{Z}^n$ as $n\rightarrow\infty$ for
a large class of distributions of passage times.
