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

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       111;

var
  f1,f2         :       text;
  n,m,k         :       longint;
  c,trace       :       array[1..MAXN,1..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i,u,v:longint;
    begin
      read(f1,n,m,k);
      for u:=1 to n do
      for v:=1 to n do
        c[u,v]:=1000111000;
      for i:=1 to m do
        begin
          read(f1,u,v,c[u,v]);
          c[v,u]:=c[u,v];
        end;
      for i:=1 to n do c[i,i]:=0;
    end;

procedure init;
    var
      i,j,k:longint;
    begin
      for i:=1 to n do
      for j:=1 to n do
        trace[i,j]:=j;

      for k:=1 to n do
        for i:=1 to n do
        for j:=1 to n do
          if c[i,j]>c[i,k]+c[k,j] then
            begin
              c[i,j]:=c[i,k]+c[k,j];
              trace[i,j]:=trace[i,k];
            end;
    end;

procedure solve;
    var
      i,q,u,v,count:longint;
    begin
      for i:=1 to k do
        begin
          read(f1,q,u,v);
          if q=0 then writeln(f2,c[u,v])
          else
            begin
              count:=1; q:=u;
              repeat
                inc(count);
                u:=trace[u,v];
              until u=v;
              write(f2,count,' ',q);
              u:=q;
              repeat
                u:=trace[u,v];
                write(f2,' ',u);
              until u=v;
              writeln(f2);
            end;
        end;
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Download