`
lovnet
  • 浏览: 6672218 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
文章分类
社区版块
存档分类
最新评论

POJ 1125(Floyd)

 
阅读更多

裸Floyd


Program P1125;
const
   maxn=100;
   maxedge=10;
   NULL=-2139062144;
var
   n,i,j,k,m,v,t,ans:longint;
   f:array[1..maxn,1..maxn] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
begin
   read(n);
   while (n<>0) do
   begin
      fillchar(f,sizeof(f),128);
      for i:=1 to n do
      begin
         f[i,i]:=0;
         read(m);
         for j:=1 to m do
         begin
            read(v,t);
            f[i,v]:=t;
         end;
      end;

      for k:=1 to n do
         for i:=1 to n do
            for j:=1 to n do
               if (f[i,k]<>NULL) and (f[k,j]<>NULL) then
                  if (f[i,k]+f[k,j]<f[i,j]) or (f[i,j]=NULL) then f[i,j]:=f[i,k]+f[k,j];
      ans:=maxlongint;

      v:=0;
      for i:=1 to n do
      begin
         t:=f[i,1];
         for j:=1 to n do
         begin
            if f[i,j]=NULL then break else t:=max(f[i,j],t);
         end;
         if f[i,j]=NULL then continue;
         if t<ans then begin v:=i; ans:=t; end;

      end;
      if (ans=maxlongint) then writeln('disjoint') else writeln(v,' ',ans);



      read(n);
   end;
end.


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics