program TSP_Dynamic_File;
 
uses
  SysUtils, Classes;
 
const
  MAXN = 5; // Максимальна кількість міст
  INF = 1000000000; // Це значення може бути дуже великим
 
// Оголошення нового типу для матриці відстаней
type
  TDistanceMatrix = array[0..MAXN-1, 0..MAXN-1] of LongInt; // Змінено на LongInt
 
var
  N: Integer; // Фактична кількість міст для розрахунку
  N_selected: Integer; // Кількість міст, яку потрібно вибрати з MAXN
  dist: TDistanceMatrix; // Використовуємо новий тип
  dp: array[0..(1 shl MAXN)-1, 0..MAXN-1] of LongInt; // Змінено на LongInt
  path: array[0..(1 shl MAXN)-1, 0..MAXN-1] of Integer; // path зберігає індекси, тому Integer підходить
  i, j, mask, last, prevMask: Integer; // prevMask не використовується, можна видалити
  cost, bestLast: LongInt; // cost може бути великим, bestLast - індекс, але для універсальності з cost можна залишити LongInt
  route: array[0..MAXN] of Integer;
  f: TextFile; // Не використовується
  s: string; // Не використовується
  sl: TStringList; // Не використовується
  parts: TStringList; // Не використовується
 
function Min(a, b: LongInt): LongInt; // Змінено на LongInt
begin
  if a < b then Min := a else Min := b;
end;
 
// Функція для генерації сталої матриці суміжності
procedure GenerateConstantDistanceMatrix(var distMatrix: TDistanceMatrix; size: Integer);
var
  row, col: Integer;
begin
  for row := 0 to size-1 do
  begin
    for col := 0 to size-1 do
    begin
      if row = col then
        distMatrix[row, col] := 0 // Відстань до себе - 0
      else
        // Приклад генерації: відстань залежить від суми індексів
        // Можете змінити цю формулу для різних наборів даних
        distMatrix[row, col] := Abs(row - col) * 5 + 10;
        // Перевірте, чи не перевищує це значення INF
        if distMatrix[row, col] > INF then distMatrix[row,col] := INF; // Обмеження, якщо генерація дає надто великі числа
    end;
  end;
end;
 
begin
  // Встановіть кількість міст, яку потрібно вибрати для розрахунку (<= MAXN)
  // Для тестування можна почати з невеликих значень, наприклад 10-15
  N_selected := 16; 
 
  if N_selected > MAXN then
  begin
    WriteLn('Помилка: N_selected не може бути більшим за MAXN.');
    ReadLn;
    Exit;
  end;
 
  N := N_selected;
 
  // Виберіть один із способів отримання матриці:
  // 1. Зчитати з файлу dist.txt (розкоментуйте цей блок)
  (*
  AssignFile(f, 'dist.txt');
  Reset(f);
  sl := TStringList.Create;
  parts := TStringList.Create;
  parts.Delimiter := ' ';
 
  for i := 0 to MAXN-1 do
  begin
    if not Eof(f) then
    begin
      ReadLn(f, s);
      sl.Add(s);
    end
    else
    begin
      sl.Add('');
      for j := 0 to MAXN-1 do
        dist[i,j] := INF;
    end;
  end;
  CloseFile(f);
 
  for i := 0 to MAXN-1 do
  begin
    if i < sl.Count then
    begin
      parts.DelimitedText := sl.Strings[i];
      for j := 0 to MAXN-1 do
      begin
        if j < parts.Count then
          dist[i,j] := StrToInt(parts.Strings[j])
        else
          dist[i,j] := INF;
      end;
    end;
  end;
 
  sl.Free;
  parts.Free;
  *)
 
  // 2. Згенерувати за допомогою функції (залишайте розкоментованим для генерації)
  GenerateConstantDistanceMatrix(dist, MAXN);
 
  // Ініціалізація dp-таблиці
  for mask := 0 to (1 shl N)-1 do
    for i := 0 to N-1 do
    begin
      dp[mask, i] := INF;
      path[mask, i] := -1;
    end;
 
  dp[1 shl 0, 0] := 0;
 
  // Динамічне програмування по підмножинах
  for mask := 0 to (1 shl N)-1 do
    for last := 0 to N-1 do
      if (mask and (1 shl last)) <> 0 then
      begin
        for j := 0 to N-1 do
          if (mask and (1 shl j)) = 0 then
          begin
            cost := dp[mask, last] + dist[last, j];
            if cost < dp[mask or (1 shl j), j] then
            begin
              dp[mask or (1 shl j), j] := cost;
              path[mask or (1 shl j), j] := last;
            end;
          end;
      end;
 
  // Пошук найкоротшого циклу (повернення в місто 0)
  cost := INF;
  bestLast := -1;
  for i := 1 to N-1 do
    if dp[(1 shl N)-1, i] + dist[i, 0] < cost then
    begin
      cost := dp[(1 shl N)-1, i] + dist[i, 0];
      bestLast := i;
    end;
 
  // Виведення мінімальної довжини маршруту
  WriteLn('Мінімальна довжина маршруту: ', cost);
 
  // Відновлення маршруту
  mask := (1 shl N)-1;
  i := bestLast;
  for j := N-1 downto 0 do
  begin
    route[j] := i;
    i := path[mask, i];
    mask := mask xor (1 shl route[j]);
  end;
  route[N] := 0; // повернення в стартове місто
 
  // Виведення маршруту
  Write('Маршрут: ');
  for i := 0 to N do
  begin
    Write(route[i], ' ');
  end;
  WriteLn;
 
  ReadLn;
end.

cHJvZ3JhbSBUU1BfRHluYW1pY19GaWxlOwoKdXNlcwogIFN5c1V0aWxzLCBDbGFzc2VzOwoKY29uc3QKICBNQVhOID0gNTsgLy8g0JzQsNC60YHQuNC80LDQu9GM0L3QsCDQutGW0LvRjNC60ZbRgdGC0Ywg0LzRltGB0YIKICBJTkYgPSAxMDAwMDAwMDAwOyAvLyDQptC1INC30L3QsNGH0LXQvdC90Y8g0LzQvtC20LUg0LHRg9GC0Lgg0LTRg9C20LUg0LLQtdC70LjQutC40LwKCi8vINCe0LPQvtC70L7RiNC10L3QvdGPINC90L7QstC+0LPQviDRgtC40L/RgyDQtNC70Y8g0LzQsNGC0YDQuNGG0ZYg0LLRltC00YHRgtCw0L3QtdC5CnR5cGUKICBURGlzdGFuY2VNYXRyaXggPSBhcnJheVswLi5NQVhOLTEsIDAuLk1BWE4tMV0gb2YgTG9uZ0ludDsgLy8g0JfQvNGW0L3QtdC90L4g0L3QsCBMb25nSW50Cgp2YXIKICBOOiBJbnRlZ2VyOyAvLyDQpNCw0LrRgtC40YfQvdCwINC60ZbQu9GM0LrRltGB0YLRjCDQvNGW0YHRgiDQtNC70Y8g0YDQvtC30YDQsNGF0YPQvdC60YMKICBOX3NlbGVjdGVkOiBJbnRlZ2VyOyAvLyDQmtGW0LvRjNC60ZbRgdGC0Ywg0LzRltGB0YIsINGP0LrRgyDQv9C+0YLRgNGW0LHQvdC+INCy0LjQsdGA0LDRgtC4INC3IE1BWE4KICBkaXN0OiBURGlzdGFuY2VNYXRyaXg7IC8vINCS0LjQutC+0YDQuNGB0YLQvtCy0YPRlNC80L4g0L3QvtCy0LjQuSDRgtC40L8KICBkcDogYXJyYXlbMC4uKDEgc2hsIE1BWE4pLTEsIDAuLk1BWE4tMV0gb2YgTG9uZ0ludDsgLy8g0JfQvNGW0L3QtdC90L4g0L3QsCBMb25nSW50CiAgcGF0aDogYXJyYXlbMC4uKDEgc2hsIE1BWE4pLTEsIDAuLk1BWE4tMV0gb2YgSW50ZWdlcjsgLy8gcGF0aCDQt9Cx0LXRgNGW0LPQsNGUINGW0L3QtNC10LrRgdC4LCDRgtC+0LzRgyBJbnRlZ2VyINC/0ZbQtNGF0L7QtNC40YLRjAogIGksIGosIG1hc2ssIGxhc3QsIHByZXZNYXNrOiBJbnRlZ2VyOyAvLyBwcmV2TWFzayDQvdC1INCy0LjQutC+0YDQuNGB0YLQvtCy0YPRlNGC0YzRgdGPLCDQvNC+0LbQvdCwINCy0LjQtNCw0LvQuNGC0LgKICBjb3N0LCBiZXN0TGFzdDogTG9uZ0ludDsgLy8gY29zdCDQvNC+0LbQtSDQsdGD0YLQuCDQstC10LvQuNC60LjQvCwgYmVzdExhc3QgLSDRltC90LTQtdC60YEsINCw0LvQtSDQtNC70Y8g0YPQvdGW0LLQtdGA0YHQsNC70YzQvdC+0YHRgtGWINC3IGNvc3Qg0LzQvtC20L3QsCDQt9Cw0LvQuNGI0LjRgtC4IExvbmdJbnQKICByb3V0ZTogYXJyYXlbMC4uTUFYTl0gb2YgSW50ZWdlcjsKICBmOiBUZXh0RmlsZTsgLy8g0J3QtSDQstC40LrQvtGA0LjRgdGC0L7QstGD0ZTRgtGM0YHRjwogIHM6IHN0cmluZzsgLy8g0J3QtSDQstC40LrQvtGA0LjRgdGC0L7QstGD0ZTRgtGM0YHRjwogIHNsOiBUU3RyaW5nTGlzdDsgLy8g0J3QtSDQstC40LrQvtGA0LjRgdGC0L7QstGD0ZTRgtGM0YHRjwogIHBhcnRzOiBUU3RyaW5nTGlzdDsgLy8g0J3QtSDQstC40LrQvtGA0LjRgdGC0L7QstGD0ZTRgtGM0YHRjwoKZnVuY3Rpb24gTWluKGEsIGI6IExvbmdJbnQpOiBMb25nSW50OyAvLyDQl9C80ZbQvdC10L3QviDQvdCwIExvbmdJbnQKYmVnaW4KICBpZiBhIDwgYiB0aGVuIE1pbiA6PSBhIGVsc2UgTWluIDo9IGI7CmVuZDsKCi8vINCk0YPQvdC60YbRltGPINC00LvRjyDQs9C10L3QtdGA0LDRhtGW0Zcg0YHRgtCw0LvQvtGXINC80LDRgtGA0LjRhtGWINGB0YPQvNGW0LbQvdC+0YHRgtGWCnByb2NlZHVyZSBHZW5lcmF0ZUNvbnN0YW50RGlzdGFuY2VNYXRyaXgodmFyIGRpc3RNYXRyaXg6IFREaXN0YW5jZU1hdHJpeDsgc2l6ZTogSW50ZWdlcik7CnZhcgogIHJvdywgY29sOiBJbnRlZ2VyOwpiZWdpbgogIGZvciByb3cgOj0gMCB0byBzaXplLTEgZG8KICBiZWdpbgogICAgZm9yIGNvbCA6PSAwIHRvIHNpemUtMSBkbwogICAgYmVnaW4KICAgICAgaWYgcm93ID0gY29sIHRoZW4KICAgICAgICBkaXN0TWF0cml4W3JvdywgY29sXSA6PSAwIC8vINCS0ZbQtNGB0YLQsNC90Ywg0LTQviDRgdC10LHQtSAtIDAKICAgICAgZWxzZQogICAgICAgIC8vINCf0YDQuNC60LvQsNC0INCz0LXQvdC10YDQsNGG0ZbRlzog0LLRltC00YHRgtCw0L3RjCDQt9Cw0LvQtdC20LjRgtGMINCy0ZbQtCDRgdGD0LzQuCDRltC90LTQtdC60YHRltCyCiAgICAgICAgLy8g0JzQvtC20LXRgtC1INC30LzRltC90LjRgtC4INGG0Y4g0YTQvtGA0LzRg9C70YMg0LTQu9GPINGA0ZbQt9C90LjRhSDQvdCw0LHQvtGA0ZbQsiDQtNCw0L3QuNGFCiAgICAgICAgZGlzdE1hdHJpeFtyb3csIGNvbF0gOj0gQWJzKHJvdyAtIGNvbCkgKiA1ICsgMTA7CiAgICAgICAgLy8g0J/QtdGA0LXQstGW0YDRgtC1LCDRh9C4INC90LUg0L/QtdGA0LXQstC40YnRg9GUINGG0LUg0LfQvdCw0YfQtdC90L3RjyBJTkYKICAgICAgICBpZiBkaXN0TWF0cml4W3JvdywgY29sXSA+IElORiB0aGVuIGRpc3RNYXRyaXhbcm93LGNvbF0gOj0gSU5GOyAvLyDQntCx0LzQtdC20LXQvdC90Y8sINGP0LrRidC+INCz0LXQvdC10YDQsNGG0ZbRjyDQtNCw0ZQg0L3QsNC00YLQviDQstC10LvQuNC60ZYg0YfQuNGB0LvQsAogICAgZW5kOwogIGVuZDsKZW5kOwoKYmVnaW4KICAvLyDQktGB0YLQsNC90L7QstGW0YLRjCDQutGW0LvRjNC60ZbRgdGC0Ywg0LzRltGB0YIsINGP0LrRgyDQv9C+0YLRgNGW0LHQvdC+INCy0LjQsdGA0LDRgtC4INC00LvRjyDRgNC+0LfRgNCw0YXRg9C90LrRgyAoPD0gTUFYTikKICAvLyDQlNC70Y8g0YLQtdGB0YLRg9Cy0LDQvdC90Y8g0LzQvtC20L3QsCDQv9C+0YfQsNGC0Lgg0Lcg0L3QtdCy0LXQu9C40LrQuNGFINC30L3QsNGH0LXQvdGMLCDQvdCw0L/RgNC40LrQu9Cw0LQgMTAtMTUKICBOX3NlbGVjdGVkIDo9IDE2OyAKCiAgaWYgTl9zZWxlY3RlZCA+IE1BWE4gdGhlbgogIGJlZ2luCiAgICBXcml0ZUxuKCfQn9C+0LzQuNC70LrQsDogTl9zZWxlY3RlZCDQvdC1INC80L7QttC1INCx0YPRgtC4INCx0ZbQu9GM0YjQuNC8INC30LAgTUFYTi4nKTsKICAgIFJlYWRMbjsKICAgIEV4aXQ7CiAgZW5kOwoKICBOIDo9IE5fc2VsZWN0ZWQ7CgogIC8vINCS0LjQsdC10YDRltGC0Ywg0L7QtNC40L0g0ZbQtyDRgdC/0L7RgdC+0LHRltCyINC+0YLRgNC40LzQsNC90L3RjyDQvNCw0YLRgNC40YbRljoKICAvLyAxLiDQl9GH0LjRgtCw0YLQuCDQtyDRhNCw0LnQu9GDIGRpc3QudHh0ICjRgNC+0LfQutC+0LzQtdC90YLRg9C50YLQtSDRhtC10Lkg0LHQu9C+0LopCiAgKCoKICBBc3NpZ25GaWxlKGYsICdkaXN0LnR4dCcpOwogIFJlc2V0KGYpOwogIHNsIDo9IFRTdHJpbmdMaXN0LkNyZWF0ZTsKICBwYXJ0cyA6PSBUU3RyaW5nTGlzdC5DcmVhdGU7CiAgcGFydHMuRGVsaW1pdGVyIDo9ICcgJzsKCiAgZm9yIGkgOj0gMCB0byBNQVhOLTEgZG8KICBiZWdpbgogICAgaWYgbm90IEVvZihmKSB0aGVuCiAgICBiZWdpbgogICAgICBSZWFkTG4oZiwgcyk7CiAgICAgIHNsLkFkZChzKTsKICAgIGVuZAogICAgZWxzZQogICAgYmVnaW4KICAgICAgc2wuQWRkKCcnKTsKICAgICAgZm9yIGogOj0gMCB0byBNQVhOLTEgZG8KICAgICAgICBkaXN0W2ksal0gOj0gSU5GOwogICAgZW5kOwogIGVuZDsKICBDbG9zZUZpbGUoZik7CgogIGZvciBpIDo9IDAgdG8gTUFYTi0xIGRvCiAgYmVnaW4KICAgIGlmIGkgPCBzbC5Db3VudCB0aGVuCiAgICBiZWdpbgogICAgICBwYXJ0cy5EZWxpbWl0ZWRUZXh0IDo9IHNsLlN0cmluZ3NbaV07CiAgICAgIGZvciBqIDo9IDAgdG8gTUFYTi0xIGRvCiAgICAgIGJlZ2luCiAgICAgICAgaWYgaiA8IHBhcnRzLkNvdW50IHRoZW4KICAgICAgICAgIGRpc3RbaSxqXSA6PSBTdHJUb0ludChwYXJ0cy5TdHJpbmdzW2pdKQogICAgICAgIGVsc2UKICAgICAgICAgIGRpc3RbaSxqXSA6PSBJTkY7CiAgICAgIGVuZDsKICAgIGVuZDsKICBlbmQ7CgogIHNsLkZyZWU7CiAgcGFydHMuRnJlZTsKICAqKQoKICAvLyAyLiDQl9Cz0LXQvdC10YDRg9Cy0LDRgtC4INC30LAg0LTQvtC/0L7QvNC+0LPQvtGOINGE0YPQvdC60YbRltGXICjQt9Cw0LvQuNGI0LDQudGC0LUg0YDQvtC30LrQvtC80LXQvdGC0L7QstCw0L3QuNC8INC00LvRjyDQs9C10L3QtdGA0LDRhtGW0ZcpCiAgR2VuZXJhdGVDb25zdGFudERpc3RhbmNlTWF0cml4KGRpc3QsIE1BWE4pOwoKICAvLyDQhtC90ZbRhtGW0LDQu9GW0LfQsNGG0ZbRjyBkcC3RgtCw0LHQu9C40YbRlgogIGZvciBtYXNrIDo9IDAgdG8gKDEgc2hsIE4pLTEgZG8KICAgIGZvciBpIDo9IDAgdG8gTi0xIGRvCiAgICBiZWdpbgogICAgICBkcFttYXNrLCBpXSA6PSBJTkY7CiAgICAgIHBhdGhbbWFzaywgaV0gOj0gLTE7CiAgICBlbmQ7CgogIGRwWzEgc2hsIDAsIDBdIDo9IDA7CgogIC8vINCU0LjQvdCw0LzRltGH0L3QtSDQv9GA0L7Qs9GA0LDQvNGD0LLQsNC90L3RjyDQv9C+INC/0ZbQtNC80L3QvtC20LjQvdCw0YUKICBmb3IgbWFzayA6PSAwIHRvICgxIHNobCBOKS0xIGRvCiAgICBmb3IgbGFzdCA6PSAwIHRvIE4tMSBkbwogICAgICBpZiAobWFzayBhbmQgKDEgc2hsIGxhc3QpKSA8PiAwIHRoZW4KICAgICAgYmVnaW4KICAgICAgICBmb3IgaiA6PSAwIHRvIE4tMSBkbwogICAgICAgICAgaWYgKG1hc2sgYW5kICgxIHNobCBqKSkgPSAwIHRoZW4KICAgICAgICAgIGJlZ2luCiAgICAgICAgICAgIGNvc3QgOj0gZHBbbWFzaywgbGFzdF0gKyBkaXN0W2xhc3QsIGpdOwogICAgICAgICAgICBpZiBjb3N0IDwgZHBbbWFzayBvciAoMSBzaGwgaiksIGpdIHRoZW4KICAgICAgICAgICAgYmVnaW4KICAgICAgICAgICAgICBkcFttYXNrIG9yICgxIHNobCBqKSwgal0gOj0gY29zdDsKICAgICAgICAgICAgICBwYXRoW21hc2sgb3IgKDEgc2hsIGopLCBqXSA6PSBsYXN0OwogICAgICAgICAgICBlbmQ7CiAgICAgICAgICBlbmQ7CiAgICAgIGVuZDsKCiAgLy8g0J/QvtGI0YPQuiDQvdCw0LnQutC+0YDQvtGC0YjQvtCz0L4g0YbQuNC60LvRgyAo0L/QvtCy0LXRgNC90LXQvdC90Y8g0LIg0LzRltGB0YLQviAwKQogIGNvc3QgOj0gSU5GOwogIGJlc3RMYXN0IDo9IC0xOwogIGZvciBpIDo9IDEgdG8gTi0xIGRvCiAgICBpZiBkcFsoMSBzaGwgTiktMSwgaV0gKyBkaXN0W2ksIDBdIDwgY29zdCB0aGVuCiAgICBiZWdpbgogICAgICBjb3N0IDo9IGRwWygxIHNobCBOKS0xLCBpXSArIGRpc3RbaSwgMF07CiAgICAgIGJlc3RMYXN0IDo9IGk7CiAgICBlbmQ7CgogIC8vINCS0LjQstC10LTQtdC90L3RjyDQvNGW0L3RltC80LDQu9GM0L3QvtGXINC00L7QstC20LjQvdC4INC80LDRgNGI0YDRg9GC0YMKICBXcml0ZUxuKCfQnNGW0L3RltC80LDQu9GM0L3QsCDQtNC+0LLQttC40L3QsCDQvNCw0YDRiNGA0YPRgtGDOiAnLCBjb3N0KTsKCiAgLy8g0JLRltC00L3QvtCy0LvQtdC90L3RjyDQvNCw0YDRiNGA0YPRgtGDCiAgbWFzayA6PSAoMSBzaGwgTiktMTsKICBpIDo9IGJlc3RMYXN0OwogIGZvciBqIDo9IE4tMSBkb3dudG8gMCBkbwogIGJlZ2luCiAgICByb3V0ZVtqXSA6PSBpOwogICAgaSA6PSBwYXRoW21hc2ssIGldOwogICAgbWFzayA6PSBtYXNrIHhvciAoMSBzaGwgcm91dGVbal0pOwogIGVuZDsKICByb3V0ZVtOXSA6PSAwOyAvLyDQv9C+0LLQtdGA0L3QtdC90L3RjyDQsiDRgdGC0LDRgNGC0L7QstC1INC80ZbRgdGC0L4KCiAgLy8g0JLQuNCy0LXQtNC10L3QvdGPINC80LDRgNGI0YDRg9GC0YMKICBXcml0ZSgn0JzQsNGA0YjRgNGD0YI6ICcpOwogIGZvciBpIDo9IDAgdG8gTiBkbwogIGJlZ2luCiAgICBXcml0ZShyb3V0ZVtpXSwgJyAnKTsKICBlbmQ7CiAgV3JpdGVMbjsKCiAgUmVhZExuOwplbmQu