存两个图论模板

kruskal
模板题 codevs1078
http://codevs.cn/problem/1078/

{
作者:CWW970329
题目:p1078 最小生成树
}

program cx;
var i,j,n,cnt,sum,top:longint;
    home,ax,ay,aw:array[0..100000]of longint;
    g:array[0..200,0..200]of longint;

procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
  i:=l; j:=r;
  x:=aw[(l+r)>>1];
  repeat
    while aw[i]<x do inc(i);
    while x<aw[j] do dec(j);
    if not(i>j) then
      begin
         y:=aw[i]; aw[i]:=aw[j]; aw[j]:=y;
         y:=ax[i]; ax[i]:=ax[j]; ax[j]:=y;
         y:=ay[i]; ay[i]:=ay[j]; ay[j]:=y;
         inc(i); j:=j-1;
      end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

function find(x:longint):longint;
begin
  if home[x]=x then exit(x);
  home[x]:=find(home[x]);
  exit(home[x]);
end;

begin
  read(n);
  for i:=1 to n do
    for j:=1 to n do  read(g[i,j]);
  for i:=2 to n do
    for j:=1 to i-1 do
      begin
        inc(cnt);
        ax[cnt]:=i;
        ay[cnt]:=j;
        aw[cnt]:=g[i,j];
      end;
  sort(1,cnt);
  for i:=1 to n do home[i]:=i;
  for i:=1 to cnt do
    begin
      if find(ax[i])=find(ay[i]) then continue;
      home[find(ax[i])]:=find(ay[i]);
      inc(sum,aw[i]);
      inc(top);
      if top=n-1 then break;
    end;
  writeln(sum);
end.

SPFA

program cx;
type node=record
      x,y:longint; end;
const big=999999999;
var i,m,n,s,o,x,y,cnt,r,f:longint;
    a:array[0..100000]of node;
    q,e,next,head:array[0..100000]of longint;
    w,dist:array[0..100000]of real;
    v:array[0..100000]of boolean;

procedure build(x,y:longint);
begin
  inc(cnt);
  e[cnt]:=y;
  next[cnt]:=head[x];
  head[x]:=cnt;
  w[cnt]:=sqrt(sqr(a[x].x-a[y].x)+
               sqr(a[x].y-a[y].y));
end;

procedure spfa;
var i,p:longint;
begin
  f:=1;
  r:=1;
  q[1]:=s;
  v[s]:=true;
  dist[s]:=0;
  while f<=r do
    begin
      p:=head[q[f]];
      while p>0 do
        begin
          if dist[q[f]]+w[p]<dist[e[p]] then
            begin
              dist[e[p]]:=dist[q[f]]+w[p];
              if not v[e[p]] then
                begin
                  inc(r);
                  q[r]:=e[p];
                  v[e[p]]:=true;
                end;
            end;
          p:=next[p];
        end;
      inc(f);
      v[q[f]]:=false;
    end;
end;

begin
  assign(input,'short.in');  reset(input);
  assign(output,'short.out');rewrite(output);
  fillchar(v,sizeof(v),false);
  cnt:=0;
  read(n);
  for i:=1 to n do read(a[i].x,a[i].y);
  for i:=1 to n do dist[i]:=big;
  read(m);
  for i:=1 to m do
    begin
      read(x,y);
      build(x,y);
      build(y,x);
    end;
  read(s,o);
  spfa;
  writeln(dist[o]:0:2);
  close(input);
  close(output);
end.