DHSERV – SPOJ

Đề bài: http://vn.spoj.com/problems/DHSERV/

Thuật toán:

• Bài này thuần sử dụng thuật toán Floyd. Các bạn có thể tham khảo code bên dưới để hiểu thêm.

Code:

const
  fi='';//hserv.inp';
  fo='';//dhserv.out';
  maxn=500;
  oo=trunc(1e18);
var
  a : array[1..maxn,1..maxn] of int64;
  d : array[1..maxn,1..maxn] of int64;
  i,j,n,m,k : longint;
procedure enter;
  var u,v,w : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m,k);
    for i:=1 to n do
      for j:=1 to n do
        if i<>j then
          begin
            d[i,j] := oo;
            a[i,j] := oo;
          end else
          begin
            d[i,j] := 0;
            a[i,j] := 0;
          end;
    for i:=1 to m do
      begin
        read(u,v,w);
        a[u,v] := w;
        d[u,v] := w;
      end;
  end;
procedure process;
  var tg,kieu,u,v,kk : longint;
  begin
    assign(output,fo);rewrite(output);
    for kk:=1 to k do
      begin
        read(kieu);
        if kieu=1 then
          begin
            read(tg);
            for u:=1 to n do
              for v:=1 to n do
                if d[u,v] > d[u,tg] + d[tg,v] then
                  begin
                    d[u,v] := d[u,tg] + d[tg,v];
                  end;
          end;
        if kieu=2 then
          begin
            read(u,v);
            if d[u,v]=oo then writeln(-1) else
            writeln(d[u,v]);
          end;
      end;
      close(output);
  end;
begin
  enter;
  process;
end.