Trở về đầu

foto1 foto2 foto3 foto4 foto5
Giảng viên
Nguyễn Tô Sơn - Thủ khoa Đại học Sư phạm Hà Nội
ĐT: 091.333.2869

HỌC TIN CÙNG THỦ KHOA

Thành công không phải đích đến, mà là cả một hành trình

Tìm kiếm

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

2. File Output

- Mỗi dòng ghi ra một đường đi từ s tới t. (Ghi ra -1 nếu không tồn tại đường đi từ s tới t)

const fi = 'CHIEUSAU.INP';
      fo = 'CHIEUSAU.OUT';
      MAXN = 20;

var n, s, t: integer;
    g: array [1..MAXN, 1..MAXN] of integer;
    cx: array [1..MAXN] of boolean;
    Truoc: array [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
        begin
                for j:= 1 to n do
                        read(f, g[i, j]);
                readln(f);
        end;
        close(f);
end;

procedure Init;
begin
        fillchar(cx, sizeof(cx), true);
end;

procedure Duyet(i: integer);
begin
        if Truoc[i] = -1 then write(f, i)
                else begin
                        Duyet(Truoc[i]);
                        write(f, ' -> ', i);
                     end;
end;

procedure InKQ;
begin
        Duyet(t);
        writeln(f);
end;

procedure DFS(u: integer); // Quay lui
var v: integer;
begin
        for v:= 1 to n do
                if cx[v] = true then
                        if g[u, v] = 1 then
                        begin
                                cx[v]:= false;
                                Truoc[v]:= u;

                                if v = t then InKQ
                                        else DFS(v);

                                cx[v]:= true; // Tra lai trang thai ban dau
                        end;
end;


BEGIN
        Nhap;
        Init;
        assign(f, fo); rewrite(f);
        Truoc[s]:= -1;
        cx[s]:= false;
        DFS(s);
        close(f);
END.

Giảng viên Nguyễn Tô Sơn, Thủ khoa Đại học Sư phạm Hà Nội. Điện thoại: 091.333.2869