FLOYD - Floyd hoặc Dijkstra ( Cơ bản )

Tác giả: ll931110

Ngôn ngữ: Pascal

Program FLOYD;
        Const
                input  = '';
                output = '';
        Var
                F,Trace: array[1..100,1..100] of longint;
                  n,m,k: longint;
                    val: array[1..100] of longint;
                  fi,fo: text;

Procedure LoadGraph;
          Var
                i,j,u,v: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);
                                Readln(fi, n, m, k);

                                For i:= 1 to n do
                                        For j:= 1 to n do if i = j then F[i,j]:= 0
                                                                   else F[i,j]:= 10000000;

                                For i:= 1 to m do
                                        Begin
                                                Readln(fi, u,v,F[u,v]);
                                                F[v,u]:= F[u,v];
                                        End;
          End;

Procedure Floyd;
          Var
                k,u,v: longint;
          Begin
                For u:= 1 to n do
                        For v:= 1 to n do Trace[u,v]:= v;

                For k:= 1 to n do
                        For u:= 1 to n do
                                For v:= 1 to n do
                                        if F[u,v] > F[u,k] + F[k,v] then
                                                Begin
                                                        F[u,v]:= F[u,k] + F[k,v];
                                                        Trace[u,v]:= Trace[u,k];
                                                End;
          End;

Procedure PrintResult;
          Var
                x,u,v,i,j,num: longint;
          Begin
                Assign(fo, output);
                        Rewrite(fo);
                                For i:= 1 to k do
                                        Begin
                                                Readln(fi, x, u, v);

                                                If x = 0 then writeln(fo, F[u,v]);
                                                If x = 1 then
                                                        Begin
                                                                num:= 0;

                                                                Repeat
                                                                        inc(num);
                                                                        val[num]:= u;
                                                                        u:= Trace[u, v];
                                                                Until u = v;

                                                                inc(num);
                                                                Write(fo, num, ' ');

                                                                For j:= 1 to num - 1 do write(fo, val[j], ' ');
                                                                Writeln(fo, v);
                                                        End;
                                        End;
                        Close(fo);
                Close(fi);
          End;

Begin
        LoadGraph;
        Floyd;
        PrintResult;
End.

Download