HỌC TIN CÙNG THỦ KHOA

Mời các bạn Download code tại: Click here

1. Dữ liệu vào:

- Dòng đầu tiên gồm duy nhất một số n là số đỉnh của đồ thị.

- n dòng tiếp theo, mỗi dòng gồm n số là ma trận trọng số của đồ thị, trong đó quy ước d[i, j] = 0 nếu không có đường đi trực tiếp từ i tới j.

2. Kết quả:

- Ghi ra chi phí ít nhất để từ đỉnh 1 qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần, rồi quay trở lại đỉnh 1.

- Hiển thị chu trình.

Program HanhTrinhNguoiDiDuLich;
uses crt;
const MAXN = 20;
      oo = MAXINT;
var n: integer;
    d: array [1..MAXN, 1..MAXN] of integer;
    a, x: array [1..MAXN] of integer;
    cx: array [1..MAXN] of boolean;
    s, smin: integer;
    dmin: integer;
    dem: integer;

procedure Nhap;
var i, j: integer;
begin
        write('Nhap N = '); readln(n);
        writeln('Nhap thong tin ve chi phi duong di: ');
        dmin:= +oo;
        for i:= 1 to n do
                for j:= 1 to n do
                begin
                        read(d[i, j]);
                        if d[i, j] <> 0 then
                                if dmin > d[i, j] then
                                        dmin:= d[i, j];
                end;
end;

procedure Init;
begin
        dem:= 0;
        fillchar(cx, sizeof(cx), true);
        cx[1]:= false;
        a[1]:= 1;
        s:= 0;
        smin:= +oo;
end;

procedure Update;
var i: integer;
begin
        if s + d[a[n], 1] < smin then
        begin
                smin:= s + d[a[n], 1];
                for i:= 1 to n do x[i]:= a[i];
        end;

end;

procedure Try2(i: integer);
var j: integer;
begin
        for j:= 1 to n do
            if cx[j] = true then
               if d[a[i-1], j] <> 0 then
               begin
                        a[i]:= j;
                        cx[j]:= false;
                        s:= s + d[a[i-1], j];
                        if s + (n-i+1)*dmin <= smin then // Nhanh can voi dieu kien chat che hon
                        // if s <= smin then
                        begin
                                if i = n then Update
                                        else  Try2(i+1);
                        end;
                        cx[j]:= true;
                        s:= s - d[a[i-1], j];

               end;
end;

procedure InKQ;
var i: integer;
begin
        writeln('Chi phi di ngan nhat la: ', smin);
        writeln('Cach di la: ');
        for i:= 1 to n do write(a[i], ' -> ');
        write(1);
end;

BEGIN
        CLRSCR;
        Nhap;
        Init;
        Try2(2);
        InKQ;
        READLN;
        READLN;
END.