unit main;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, StdCtrls, ComCtrls;

type
  TfmMain = class(TForm)
    Grid: TStringGrid;
    PathList: TListView;
    GoButt: TButton;
    edNumNodes: TEdit;
    Label1: TLabel;
    Complete: TButton;
    Clear: TButton;
    Check: TButton;
    procedure GoButtClick(Sender: TObject);
    procedure FormCreate(Sender: TObject);
  private
    procedure CalcCost(Current : string; Next : char; Rest : string;
      Cost : Integer);
    procedure CheckBest(Path : string; Cost : integer);
    procedure AddPath(Path : string; Cost : integer);
  public
    { Public declarations }
  end;

var
  fmMain: TfmMain;

implementation

{$R *.dfm}

var
  best : integer;

procedure TfmMain.GoButtClick(Sender: TObject);
var
  Range : string;
  i : integer;
begin
  Best := 0;
  Range := '';
  for i := 2 to StrToInt(edNumNodes.text) do
    Range := Range + IntToStr(i);
  CalcCost('','1',range,0);
end;



procedure TfmMain.CalcCost(Current: string; Next: char; Rest: string;
  Cost: Integer);
var
  TmpRest : string;
  i, len : integer;
  TmpNext, Last : char;
begin
  Len := Length(Current);
  If len <> 0 then begin
    Last := Current[len];
    Cost := Cost + StrToInt(Grid.Cells[StrToInt(Last),StrToInt(Next)]);
  end;
  Current := Current + Next;
  If Length(rest) < 1 then begin
    CheckBest(Current,Cost);
    exit;
  end;
  for i := 1 to Length(rest) do begin
    TmpNext := Rest[i];
    TmpRest := Rest;
    Delete(TmpRest,i,1);
    CalcCost(Current, TmpNext, TmpRest, Cost);
  end;
end;

procedure TfmMain.FormCreate(Sender: TObject);
var
  i : integer;
begin
  best := 0;
  for i := 1 to 7 do begin
    Grid.Cells[i,0] := IntToStr(i);
    Grid.Cells[0,i] := IntToStr(i);
    Grid.Cells[i,i] := '-';
  end;
end;

procedure TfmMain.CheckBest(Path: string; Cost: integer);
var
  First, Last : char;
begin
  First := Path[1];
  Last := Path[Length(Path)];
  Cost := Cost + StrToInt(Grid.Cells[StrToInt(first),StrToInt(last)]);

  if Best = 0 then begin
    PathList.Clear;
    AddPath(Path, Cost);
  end
  else if Cost < Best then begin
    PathList.Clear;
    AddPath(Path, Cost);
  end
  else if Cost = Best then begin
    AddPath(Path, Cost);
  end;


end;

procedure TfmMain.AddPath(Path: string; Cost: integer);
var
  Item : TListItem;
begin
  Best := cost;
  Item := PathList.Items.Add;
  Item.Caption := Path;
  Item.SubItems.Add(IntToStr(cost));
end;

end.