Имеется N населённых пунктов, пронумерованных от 1 до N. Некоторые пары населенных пунктов соединены дорогами. Известны стоимости проездов по
этим дорогам. Определить, можно ли попасть по этим дорогам из первого
пункта в N-ный. Если да, то найти маршрут с минимальной стоимостью
проезда.
program proezd;
const
Max = 5;
var
A: Array[1..Max, 1..Max] Of Integer;
{ *Матрица расстояний между городами. *}
f: text;
N: integer;
B: Array[1..Max, 1..Max] Of Byte;{^Вспомогательный
массив, элементы каждой строки матрицы
сортируются в порядке возрастания, но сами
элементы не переставляются, а изменяются
в матрице В номера столбцов матрицы А.*}
Way, BestWay: Array[1..Max] Of Byte;{*Хранится
текущее решение и лучшее решение. *}
Nnew: Array[1..Max] Of Boolean;{*3начение
элемента массива False говорит о том,
что в соответствующем городе коммивояжер
уже побывал. *}
BestCost: Integer;{*Стоимость лучшего решения. *}
procedure Solve(v, Count: Byte; Cost: Integer);
{*v - номер текущего города; Count - счетчик числа
пройденных городов; Cost - стоимость текущего
решения. *}
var
i: Integer;
begin
if Cost > BestCost Then Exit;{*Стоимость текущего
решения превышает стоимость лучшего из
ранее полученных. *}
if Count = N Then begin
Cost := Cost + A[v, 1];
Way [N]:= v;{*Последний город
пути. Добавляем к решению стоимость
перемещения в первый город и сравниваем
его с лучшим из ранее полученных. *}
if Cost < BestCost Then begin
BestCost := Cost;
BestWay := Way; end;
Exit;{*Оператор нарушает структурный стиль
программирования ~ "любой фрагмент логики
должен иметь одну точку входа и одну точку
выхода. Следует убрать его" . *}
end;
Nnew [v]:= False;
Way [Count]:= v;{*Город с номером v
пройден, записываем его номер в путь
коммивояжера. *}
for i := 1 To N do
if Nnew[B[v, i]] Then Solve(B[v, i],
Count + 1, Cost + A[v, B[v, i]]); {*Поиск города, в который
коммивояжер может пойти из города,
с номером v.*}
Nnew [v]:= True; {^Возвращаем город с номером v
в число непройденных. *}
end;
var
i, j: integer;
begin
assign(f, 'f:\1.txt');
reset(f);
i := 1;
j := 1;
while not eof(f) do
begin
while not eoln(f) do
begin
read(f, a[i, j]);
inc(j);
end;
readln(f);
inc(i);
end;
solve();
writeln('лучшая цена-', BestCost);
end.
Просьба исправить и доработать
|
|
|
|
Цитата (ritmix93) Просьба исправить и доработать
А что тут не правильно работает? Что доработать?
Нужна помощь? Сюда: vkontakte.ru/berestovskiy
|
|
|
|
|
не запускается даже прога. Попробуйте скопировать в паскаль. Там ошибки и недоработки
|
|
|
|
