Интересная проблема минимальной цены

Question

Есть n автобусных остановок, и мы знаем цену между i-й и j-й остановками. Это дорога с односторонним движением. Какова минимальная цена маршрута от 1-й до n-й остановки с учетом всех возможных соединений? Время и потребление памяти должны быть как можно меньше.

p.s. Например, есть 4 остановки. У нас есть такая таблица цен:

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

для перехода с 1-го на 4-й без остановок мы платим 7 $. если мы меняем маршруты на второй остановке, мы платим 3 $ + 1 $ = 4 $, чтобы доехать до третьей остановки, но мы платим на 2 $ больше, если мы доберемся до конца, поэтому в целом это будет стоить 6 $, но снова, если Смена маршрута на 3-й остановке платит 4 + 1 = 5 $.

Answer 1

Пусть d[i][j] - данные цены, а l[k] - минимальная общая стоимость перехода от k до n.Тогда

l[n] = 0

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

Время работы O (n ^ 2).(И, как указал @Henrik, это оптимально.)

Answer 2

Это стандартный поиск пути в ориентированном графе. Алгоритм Дейкстры, который находит кратчайшие пути от источника ко всем остальным узлам, - лучшее, что вы можете сделать.