нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции
рассмотрим таблицу 1:
из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)
A
B
C
D
Е
A
3
1
предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4
A
B
C
D
Е
C
3
4
2
таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7
кроме того, из С можно ехать не сразу в В, а сначала в Е:
A
B
C
D
Е
C
3
4
2
а затем из Е – в В (стоимость также 2),
A
B
C
D
Е
Е
2
2
так что общая стоимость этого маршрута равна 3 +2 + 4 = 7
теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:
A
B
C
D
Е
D
1
таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется
A
B
C
D
Е
A
3
1
A
B
C
D
Е
C
3
4
2
A
B
C
D
Е
C
3
4
2
а затем из Е – в В (стоимость также 2),
A
B
C
D
Е
Е
2
2
так что общая стоимость этого маршрута равна 3 +2 + 4 = 7
A
B
C
D
Е
D
1
A
B
C
D
Е
A
3
1
4
B
4
2
C
3
4
2
D
1
Е
4
2
2