NP-hardness for one-dimensional facility location problem with entrance fee for each customer
$\require{cancel}$
The answer shows a reduction to the rainbow path problem and thus doesn't prove anything about the complexity of the given problem. See this paper which contains hardness results for related problems (theorem 2.3 states that rainbow s-t path is hard).
The problem is $\cancel{\text{still polynomial}}$, as it can still be reduced to some version of shortest path. Observe that there always exists an optimal solution where the facilities are a subset of $\{x_1,...,x_n\}$ (given an optimal solution and a facility $y_j$ in it, let $A_j$ denote the set of clients attending $y_j$, then replacing $y_j$ with the median of $A_j$ does not increase the value of the solution). Now construct a directed graph whose vertices are $V=\{s,t, v_{il}| i\in[n], l\in[m] \}$ and whose edges are given by:
$$E=\{(v_{il},v_{jk})| i&lt;j\in[n], \text{and } l,k\in[m]\}\cup\{(s,v_{il})|i\in[n],l\in[m]\}\\\cup\{(v_{n,l},t) |l\in[m]\}$$
Interpret the edge $(v_{il},v_{jk})$ as choosing a solution where the clients $x_{i+1},...,x_j$ are members of the facility $y_k$. With this in mind, we set the weights of the edges to be:
$$
w(v_{il},v_{jk})=\sum\limits_{q=i+1}^j |x_q-m_{ij}|+(j-i)f_k\\
w(s,v_{il})=\sum\limits_{q=1}^i|x_q-m_{0,i}|+if_l\\
w(v_{n,l},t)=0, \text{ for all $l\in[m]$}
$$
Where $m_{ij}$ is the median of $x_{i+1},...,x_j$. An optimal solution for your problem is the weight of the lightest path from $s$ to $t$ of length $\le m$ which uses at most one edge from the set $E_i=\left\{(v,v_{l,i})|v\in V, l\in [n]\right\}$ for every $i\in[m]$ (this implies that we do not use the same facility twice). This version of shortest (lightest) path can be solved in polynomial time (think of it as having $m$ different color edges, and we want a path that does not use the same color twice, I believe that a sort of modified Dijkstra should work).