Interesting min price problem

There are n bus stops and we know the fee between i-th and j-th stops. It's a one-way road. What is the min price of the route from 1-st to n-th stops considering all possible connections? Time and memory consumption should be the least possible.

p.s. To give an example, say, there are 4 stops. We have such a table of prices:

. 3$ 5$ 7$
. .  1$ 3$
. .  .  1$

to go from 1-st to 4-th with no stops we pay 7开发者_运维技巧$. if we change routes on the second stop we pay 3$+1$ = 4$ to drive to the 3rd stop, but we pay 2$ more if we go to the end, so overall it will cost 6$, but again if we change routes on the 3-rd stop, we would pay 4+1=5$.

Let d[i][j] be the given prices, and l[k] the minimal overall cost to go from k to n. Then

l[n] = 0

l[k] = min(d[k][i] + l[i], i=k+1..n)

The running time is O(n^2). (And, as @Henrik pointed out, it's optimal.)

This is a standard weighted directed graph path search. Dijkstra's algorithm which finds the shortest paths from the source to all other nodes is the best you can do.