Find an efficient algorithm on shortest path $l$ while at most $C$ cost a graph $G$, each edge $e$ has two parameters: l(e) is the length and c(e) is the cost; both are nonnegative. Given a starting vertex $s$, find the shortest total length path to a destination vertex $t$ such that the total cost along this path is at most C.
My attempt:
Use Bellman-Ford algorithm to, iterate $V$ times to get the short path from $s$ to $t$. Meanwhile store every path that costs less than $C$ when updating $t$. After iteration, I compare those paths to get the shortest paths with at most $C$ cost.
This runs $O(V \times E)$. I feel it's not elegant because of its complexity.
Is there a more efficient way or new algorithm to do this?
 A: I know in case the cost is enumerable (e.g. $C$ and the cost on every edge are integers), one can do it by splitting every point into $C$ points and then applying Dijkstra's algorithm. But in case the cost is not enumerable, or if it's computationally expensive to quantize the cost and split the vertices, we would have to try something else.
I tried two heuristics and failed. Number one was to minimize $l+\lambda C$ using Dijkstra and then find the smallest $\lambda>0$ that produces a path that is within budget. The problem with this algorithm is that sometimes the possibility frontier of $(l,C)$ is not concave. Therefore, as one tunes the value of $\lambda$, it's possible to jump from one extremely long path with low cost to another extremely costly path with short distance without going through the middle grounds.
Then I tried the network flow idea. Let the in-flow be $1$ unit into the starting point and the out-flow be $1$ unit out of the destination. The classical shortest path problem would automatically give a flow that only follows one path - the shortest path. In case there are multiple shortest paths, only those flows that follow one path would be on a vertex of the feasible region. So any linear programming (LP) solver that only lands on vertices would give a flow that follows only one path, which is at the same time shortest. But once there's the cost budget, although the LP solver still finds a solution, it need not follow only one path any more.
So I'm not sure if a polynomial-time algorithm exists for this shortest path problem with an upper bound for the cost budget.
A: The problem is known as the Constrained shortest path problem. It is $\mathsf{NP}$-hard as mentioned in the paper "Resource Constrained Shortest Paths" (by Kurt Mehlhorn1 and Mark Ziegelmann). The $\mathsf{NP}$-hardness proof is given in the paper: "A dual algorithm for the constrained shortest path problem" (by Gabriel Y. Handler, Israel Zang)
A: This problem is NP-hard as one may reduce the Partition Problem to it.
For a set $S=\{a_1, \dots, a_n\}$ and a map function $s:S\rightarrow N^+$ and $A=\sum_{a\in S} s(a)$, the partition problem asks whether whether there is $S' \subseteq S $ s.t. $\sum_{a\in S'} s(a) = A/2$. 
Create n+1 node, $B_1, \dots, B_{n+1}$, add two edges from $B_i$ to $B_{i+1}$, one edge costs $s(a_i) + 1$ with distance $1$, the other costs $1$ with distance $s(a_i) + 1$ (of course one may replace the parallel edges by adding an intemediate node).  Let $C$ be $A/2 + n$, and if the minimum distance from $B_1$ to $B_n$ can reach $A/2 + n$ within cost of $C$, there will be a valid partition.
