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

2. File Output

- Ghi ra đường đi qua ít đỉnh trung gian nhất 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 = 'CHIEURONG.INP';
      fo = 'CHIEURONG.OUT';
      MAXN = 10000;

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;
    Q: array [1..MAXN] of integer;
    Qf, Ql: 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);
        Qf:= 1;
        Ql:= 0;
end;

procedure Push(i: integer);
begin
        inc(Ql);
        Q[Ql]:= i;
end;

function Pop: integer;
begin
        Pop:= Q[Qf];
        inc(Qf);

end;

function Empty: boolean;
begin
        exit(Qf > Ql);
end;

procedure BFS;
var u, v: integer;
begin
        Push(s);
        cx[s]:= false;
        Truoc[s]:= -1;
        repeat
                u:= Pop;
                for v:= 1 to n do
                        if cx[v] then
                                if g[u, v] = 1 then
                                begin
                                        Push(v);
                                        cx[v]:= false;
                                        Truoc[v]:= u;
                                        if v = t then exit;
                                end;
        until Empty;
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
        if cx[t] = true then writeln(f, -1)
                else Duyet(t);
        writeln(f);
end;


BEGIN
        Nhap;
        Init;
        BFS;
        assign(f, fo); rewrite(f);
        InKQ;
        close(f);
END.