haihongyuan.com

# noip 每日整理

From 高级本P95

5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5

3 5 1 5 代码：（floyd算法、求任意两点间的最短路径） type

node=record

x,y:integer;

end;

var

g:array[1..100,1..100] of real;

a:array[1..100] of node;

n,m,x,y,i,j,s,k,t:integer;

function distance(i,j:integer):real;

begin

distance:=sqrt(sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y)); end;

begin

for i:=1 to n do

for i:=1 to n do

for j:=1 to n do

g[i,j]:=maxint;

for i:=1 to m do

begin

g[x,y]:=distance(x,y);

g[y,x]:=g[x,y];

end;

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (g[i,k]+g[k,j]<g[i,j]) then

g[i,j]:=g[i,k]+g[k,j];

writeln(g[s,t]:0:2);

End.

From 高级本P97

3

0 1 2

1 0 1

2 1 0

2

g:array[1..100,1..100] of integer;

l:array[0..100] of integer;

u:array[0..100] of boolean;

n,i,j,k,total:integer;

begin

for i:=1 to n do

for j:=1 to n do

fillchar(l,sizeof(l),\$7F);

l[1]:=0;

fillchar(u,sizeof(u),1);

for i:=1 to n do

begin

k:=0;

for j:=1 to n do

if u[j] and (l[j]<l[k]) then k:=j;

u[k]:=false;

for j:=1 to n do

if u[j] and (g[k,j]<l[j]) then l[j]:=g[k,j]; end;

total:=0;

for i:=1 to n do

inc(total,l[i]);

writeln(total);

end.