  Coudert et al. (SODA'18) proved that under the Strong Exponential-Time
Hypothesis, for any $\epsilon >0$, there is no ${\cal
O}(2^{o(k)}n^{2-\epsilon})$-time algorithm for computing the diameter within
the $n$-vertex cubic graphs of clique-width at most $k$. We present an
algorithm which given an $n$-vertex $m$-edge graph $G$ and a $k$-expression,
computes all the eccentricities in ${\cal O}(2^{{\cal O}(k)}(n+m)^{1+o(1)})$
time, thus matching their conditional lower bound. It can be modified in order
to compute the Wiener index and the median set of $G$ within the same amount of
time. On our way, we get a distance-labeling scheme for $n$-vertex $m$-edge
graphs of clique-width at most $k$, using ${\cal O}(k\log^2{n})$ bits per
vertex and constructible in ${\cal O}(k(n+m)\log{n})$ time from a given
$k$-expression. Doing so, we match the label size obtained by Courcelle and
Vanicat (DAM 2016), while we considerably improve the dependency on $k$ in
their scheme. As a corollary, we get an ${\cal O}(kn^2\log{n})$-time algorithm
for computing All-Pairs Shortest-Paths on $n$-vertex graphs of clique-width at
most $k$. This partially answers an open question of Kratsch and Nelles
(STACS'20).
