HỌC TIN CÙNG THỦ KHOA

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

1. File Input: Click here

- Dòng đầu tiên gồm 3 số n, s, t tương ứng là số đỉnh, đỉnh bắt đầu và đỉnh kết thúc để tìm đường đi dài nhất từ s tới t.

- 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 a[i, j] = 0 nếu không có đường đi trực tiếp từ i tới j.

2. File Output

- Ghi ra độ dài đường đi dài nhất từ s tới t.

- Hiển thị đường đi dài nhất từ s tới t (mỗi đỉnh xuất hiện đúng một lần trên đường đi).

Chú ý: Thuật toán chỉ áp dụng cho đồ thị có hướng, không chứa chu trình.

Program ThuatToanFloyd;
{ Tim duong di dai nhat tren do thi co huong, khong co chu trinh, moi dinh xuat hien dung mot lan tren duong di }
const fi = 'FLOYD.INP';
      fo = 'FLOYD.OUT';
      MAXN = 100;
      VoCung = MAXINT div 2;
var a: array [1..MAXN, 1..MAXN] of integer;
    n, s, t: integer;
    Truoc: array [1..MAXN, 1..MAXN] of integer;
    f: text;

    procedure Nhap;
    var i, j: integer;
    begin
        assign(f, fi); reset(f);
        readln(f, n, s, t);
        for i:= 1 to n do
                for j:= 1 to n do
                begin
                        read(f, a[i, j]);
                        a[i, j]:= -a[i, j];
                        Truoc[i, j]:= i;
                        if (a[i, j] = 0) and (i <> j) then
                                a[i, j]:= +VoCung;
                end;
        close(f);
    end;

    procedure Floyd;
    var k, u, v: integer;
    begin
        for k:= 1 to n do
                for u:= 1 to n do
                        for v:= 1 to n do
                                  if a[u, v] > a[u, k] + a[k, v] then
                                  begin
                                        a[u, v]:= a[u, k] + a[k, v];
                                        Truoc[u, v]:= Truoc[k, v];
                                  end;
    end;

    procedure TruyVet(u, v: integer);
    var k: integer;
    begin
        k:= Truoc[u, v];
        if k = u then
                write(f, ' -> ', v)
                else
                begin
                        TruyVet(u, k);
                        TruyVet(k, v);
                end;
    end;

    procedure KetQua;
    begin
        assign(f, fo); rewrite(f);
        writeln(f, -a[s, t]);
        write(f, s);
        TruyVet(s, t);
        close(f);
    end;

BEGIN
        Nhap;
        Floyd;
        KetQua;
END.