Trở về đầu
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.