I don't have time to come up with and write out a full proof right now, but I can think of a reduction from 3SAT that I believe will work. Suppose we have $m$ variables $x_1, \dots, x_m$ and $n$ clauses $(a_{i1} \vee a_{i2} \vee a_{i3})$, $1 \le i \le n$, $a_{ij} \in \bigcup_{1 \le j \le m}\{x_j, \bar x_j\}$. Basically, for each clause in the 3SAT instance, we make a gadget consisting of 3 paths, each containing $n$ edges and corresponding to a literal in the clause, as well as a source vertex that is connected to each of the 3 "leftmost" vertices of the paths and a target vertex that is connected to each of the 3 "rightmost" vertices of the paths. All these edges can be given unit weight. String these gadgets together "in series" -- that is, use the target vertex of the first clause's gadget as the source vertex of the second clause's gadget, etc. Finally, add an edge with huge weight between the very first source vertex and the very last target vertex. I believe that, after also constructing a partition $S$ of the edges as I describe below, the 3SAT instance will be satisfiable if and only if there is a path from the very first gadget's source vertex to the very last gadget's target vertex that is shorter than the path consisting of the single, huge-weight edge just mentioned.
The $j$-th path in the gadget for the $i$-th clause, $1 \le j \le 3$, will consist of the $n+1$ vertices $v_{i,j,1}, \dots, v_{i,j,n+1}$. The trick is to assign edges in these paths to parts in the partition $S$ in such a way that, if some clause uses an edge for some literal $x$, then no clause can construct a whole path for the negative of that same literal, $\bar x$: this will express the fundamental constraint of 3SAT, which is that no variable can be simultaneously TRUE and FALSE. (Note that $x$ may itself be a negative literal; $\bar{\bar x} = x$.)
To this end, notice that in order to build a path between the source and target of some clause's gadget, we need to use every edge on one of its 3 paths. So the core idea is: Each edge taken on the $x_p$-path in some clause forbids some edge on the $\bar x_p$-path in every clause that has such a path. Specifically, the $k$-th edge on the $x_p$-path in clause $i$ forbids the $i$-th edge on the $\bar x_p$-path in clause $k$, and vice versa, whenever both edges exist. We can achieve this by creating $mn^2$ parts $s_{p,i,k}$ in $S$, with $1 \le p \le m$ and $1 \le i, k \le n$ and assigning:
- any edge $(v_{i,j,k}, v_{i,j,k+1})$ corresponding to a positive literal $x_p$ to part $s_{p,i,k}$, and
- any edge $(v_{i',j',k'}, v_{i',j',k'+1})$ corresponding to a negative literal $\bar x_p$ to part $s_{p,k',i'}$ (note the permuted indices).
Assuming that no variable appears more than once in any clause (if this actually happens, it can be easily remedied with standard techniques), from this construction it should be clear that at most one positive-literal edge and at most one negative-literal edge can appear in any specific part $s_{p,i,k}$, so no $x_i$-edge conflicts with any other $x_i$-edge (in any clause), and no $\bar x_i$-edge conflicts with any other $\bar x_i$-edge (in any clause).
The remaining edges (which connect source or target vertices to path vertices) can all be put in additional singleton parts in $S$, which allows them to be chosen freely.
