Is this problem #P-hard and why?
I show a reduction from positive partitioned 2-DNF assignment counting (see proof of 5.1 in [http://www.vldb.org/conf/2004/RS22P1.PDF] for details and inspiration of my proof). This problem asks to count the number of valuations that satisfy a formula of the form $\Phi: \bigvee_{(i,j) \in E} X_i Y_j$ with $E \subseteq \mathbb{N}^2$, where the $X_i$ and $Y_j$ are pairwise distinct variables.

Represent the positive partitioned 2-DNF as one vertex $x_i$ per variable $X_i$ and one vertex $y_j$ per variable $X_j$ and an edge from $x_i$ to $y_j$ for each $(i, j) \in E$.

I add a source vertex $s$ and an edge from $s$ to each $x_i$ with parameter $p=1/2$, so with probability $1/2$ the distance is $1$ and with probability $1/2$ it is $&gt;1$. Likewise I add an edge from each $y_j$ to the target vertex $t$ with the same distribution. Up to the exact value of edges with length $&gt;1$, is a clear probability-preserving bijection between valuations of the $X_i$ and $Y_j$ and possible worlds of this graph: for a valuation $\nu$, the corresponding graph is the one where the probabilistic edge adjacent to $X_i$ has length $1$ iff $\nu(X_i) = 1$ and length $&gt;1$ otherwise, and likewise for the $Y_j$.

I set $k=3$. I claim that the probability that there is a path from $s$ to $t$ is the number of valuations that satisfy $\Phi$ divided by $2^N$, where $N$ is the number of variables. Indeed this is clear as a valuation is true iff some adjacent pair of $X_i$ and $Y_j$ is true iff the incident edges to the corresponding $x_i$ and $y_j$ both have length $1$ in the corresponding world.
Note that the exact length of any edge of length $&gt;1$ is irrelevant as the structure of the graph ensures it can never be part of a path of length $3$ from $s$ to $t$: there are only edegs from $s$ to the $x_i$, from the $x_i$ to the $y_j$, and from the $y_j$ to $t$.