裸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.
分享到:
相关推荐
北大POJ1125-Stockbroker Grapevine【Floyd】 解题报告+AC代码
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
北大POJ2240-Arbitrage【Floyd】 解题报告+AC代码
北大POJ2253-Frogger【Floyd】 解题报告+AC代码
pku online judge 通过源码 C/C++
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
sjdlkjf;lksajflkjsdkfjs;jfklsdf
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) ...
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等