QBAGENTS – spoj

Đề bài:

Thuật toán:

  • BFS

Code:

uses    math;
const   fi='';
        fo='';
        maxn=300;
        maxm=maxn*maxn;
        oo=trunc(1e9);
type    Tq      =record
                u1,u2,k :longint;
                end;
var     q       :array[1..2*maxn*maxn*10] of Tq;
        cx      :array[1..maxn,1..maxn,1..2] of boolean;
        f       :array[1..maxn,1..maxn,1..2] of longint;
        i,j,n,m,s,t     :longint;
        dau,cuoi,res    :longint;
        // danh sach
        link,head,ke    :array[1..maxm] of longint;
procedure enter;
var     u,v     :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m,s,t);
        for i:=1 to m do
                begin
                        read(u,v);
                        link[i] := head[u];
                        head[u] :=i;
                        ke[i] := v;
                end;
        close(input);
end;
procedure push(x,y,z:longint);
begin
        inc(cuoi);
        q[cuoi].u1:=x;
        q[cuoi].u2:=y;
        q[cuoi].k:=z;
end;
procedure process;
var     v1,v2,u1,u2,k :longint;
begin
        dau :=1; cuoi :=0;
        push(s,t,1);
        fillchar(cx,sizeof(cx),true);
        //
        for i:=1 to n do
                for j:=1 to n do
                        for k:=1 to 2 do
                                f[i,j,k] := oo;
        f[s,t,1] := 0;
        while dau<=cuoi do
                begin
                        u1 := q[dau].u1;
                        u2 := q[dau].u2;
                        k := q[dau].k;
                        inc (dau);
                        if k=1 then
                                begin
                                        i := head[u1];
                                        while i>0 do
                                                begin
                                                        v1 := ke[i];
                                                        if cx[v1,u2,2] then
                                                          begin
                                                                f[v1,u2,2] := min(f[v1,u2,2],f[u1,u2,1]+1);
                                                                push(v1,u2,2);
                                                                cx[v1,u2,2] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                        if k=2 then
                                begin
                                        i := head[u2];
                                        while i>0 do
                                                begin
                                                        v2 := ke[i];
                                                        if cx[u1,v2,1] then
                                                          begin
                                                                f[u1,v2,1] := min(f[u1,u2,2]+1,f[u1,v2,1]);
                                                                push(u1,v2,1);
                                                                cx[u1,v2,1] := false;
                                                          end;
                                                        i:= link[i];
                                                end;
                                end;
                end;
        res := oo;
        for i:=1 to n do
                res := min(res,f[i,i,1]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        if res=oo then write(-1) else write(res div 2);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*