fence6.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:fence6
}

program fence6;
const
  maxn=100;
var
  fin,fout:text;
  len:array[1..maxn]of byte;
  adj:array[1..maxn,1..maxn]of 0..2;
  same:array[1..maxn*2,1..maxn*2]of boolean;
  ver:array[1..maxn*2]of byte;
  p:array[1..maxn,1..maxn]of integer;{Distance between vertexes}
  n,vers,i,j,s,l,n1,n2:byte;
  min,tmp:integer;
function edge2pnt(x,e:byte):byte;
  begin
    if e=1 then edge2pnt:=x*2-1 else edge2pnt:=x*2;
  end;
procedure recurse(x:byte);
  var
    i:byte;
  begin
    ver[x]:=vers;
    for i:=1 to n*2 do
      if (ver[i]=0) and same[x,i] then recurse(i);
  end;
procedure dijkstra(a,b:byte);
  var
    dist:array[1..maxn]of integer;
    s:set of 1..maxn;
    newadd,i:byte;
    mincost:integer;
  begin
    for i:=1 to vers do
      dist[i]:=maxint;
    dist[a]:=0;
    s:=[a];
    newadd:=a;
    repeat
      for i:=1 to vers do
        if dist[newadd]+p[newadd,i]<dist[i] then dist[i]:=dist[newadd]+p[newadd,i];
      mincost:=maxint;
      for i:=1 to vers do
        if not (i in s) then
          if dist[i]<mincost then begin
            newadd:=i;
            mincost:=dist[i];
          end;
      s:=s+[newadd];
    until (newadd=b) or (mincost=maxint);
    if b in s then
      if dist[b]+tmp<min then min:=dist[b]+tmp;
  end;
begin
  {Load info}
  fillchar(adj,sizeof(adj),0);
  assign(fin,'fence6.in');
  reset(fin);
  readln(fin,n);
  for i:=1 to n do begin
    readln(fin,s,l,n1,n2);
    len[s]:=l;
    for j:=1 to n1 do begin
      read(fin,l);
      adj[s,l]:=1;
    end;
    for j:=1 to n2 do begin
      read(fin,l);
      adj[s,l]:=2;
    end;
  end;
  close(fin);

  {Merge ends}
  fillchar(same,sizeof(same),0);
  for i:=1 to n do
    for j:=1 to n do
      if adj[i,j]>0 then
        same[edge2pnt(i,adj[i,j]),edge2pnt(j,adj[j,i])]:=true;

  fillchar(ver,sizeof(ver),0);
  vers:=0;
  for i:=1 to n*2 do
    if ver[i]=0 then begin
      inc(vers);
      recurse(i);
    end;

  {Init graph}
  for i:=1 to vers do
    for j:=1 to vers do
      if i=j then p[i,j]:=0 else p[i,j]:=maxint;
  for i:=1 to n do begin
    p[ver[i*2-1],ver[i*2]]:=len[i];
    p[ver[i*2],ver[i*2-1]]:=len[i];
  end;

  {Calculate min loop}
  min:=maxint;
  for i:=1 to vers do
    for j:=1 to vers do
      if (i<>j) and (p[i,j]<maxint) then begin
        tmp:=p[i,j];
        p[i,j]:=maxint;
        dijkstra(i,j);
        p[i,j]:=tmp;
      end;

  assign(fout,'fence6.out');
  rewrite(fout);
  writeln(fout,min);
  close(fout);
end.