usaco 2_4_4 bessie come home 题解_leokan的blog.mht

美国USACO题库源程序

    fscanf(fin, "%d\n", &npath);
    for(i=3D0; i<npath; i++) {
 fscanf(fin, "%c %c %d\n", &a, &b, &d);
 a =3D char2num(a);
 b =3D char2num(b);
 if(dist[a][b] > d)
     dist[a][b] =3D dist[b][a] =3D d;
    }

    /* floyd warshall all pair shortest path */
    for(k=3D0; k<52; k++)
    for(i=3D0; i<52; i++)
    for(j=3D0; j<52; j++)
 if(dist[i][k]+dist[k][j] < dist[i][j])
     dist[i][j] =3D dist[i][k]+dist[k][j];

    /* find closest cow */
    m =3D INF;
    a =3D '#';
    for(i=3D'A'; i<=3D'Y'; i++) {
 d =3D dist[char2num(i)][char2num('Z')];
 if(d < m) {
     m =3D d;
     a =3D i;
 }
    }

    fprintf(fout, "%c %d\n", a, m);
    exit(0);
}
</STRONG></PRE>
      <H2>Analysis of and code for Bessie Come Home by Wouter Waalewijn =
of The=20
      Netherlands</H2>
      <P><STRONG>When looking at the problem the first thing you can =
conclude is=20
      that for the solution you will need to know all the distances from =
the=20
      pastures to the barn. After calculating them you only have to =
check all=20
      these distances and pick out the nearest pasture with a cow in it, =
and=20
      that's all. </STRONG></P>
      <P><STRONG>Because the amount of vertices (=3Dpastures+barn) is =
small,=20
      running Floyd/Warshall algorithm will solve the problem easily in =
time. If=20
      you think programming Floyd/Warshall is easier than Dijkstra, just =
do it.=20
      But you can also solve the problem running Dijkstra once, which of =
course=20
      speeds up your program quite a bit. Just initialise the barn as =
starting=20
      point, and the algorithm will find the distances from the barn to =
all the=20
      pastures which is the same as the distances from all the pastures =
to the=20
      barn because the graph is undirected. Using dijkstra for the =
solution=20
      would make far more complex data solvable within time. Here below =
you can=20
      see my implementation of this solution in Pascal. It might look =
big, but=20
      this way of partitioning your program keeps it easy to debug.=20
</STRONG></P><PRE><STRONG>Var Dist:Array [1..58] of LongInt;      {Array =
with distances to barn}
    Vis :Array [1..58] of Boolean;      {Array keeping track which
pastures visited}
    Conn:Array [1..58,1..58] of Word;   {Matrix with length of edges, 0 =
=3D no edge}

Procedure Load;
Var TF   :Text;
    X,D,E:Word;
    P1,P2:Char;

Begin
 Assign(TF,'comehome.in');
 Reset(TF);
 Readln(TF,E);                          {Read number of edges}
 For X:=3D1 to E do
 Begin
  Read(TF,P1);                          {Read both pastures and edge
length}
  Read(TF,P2);
  Read(TF,P2);      {Add edge in matrix if no edge between P1 and P2 yet =
or}
  Readln(TF,D);     {this edge is shorter than the shortest till now}
  If (Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]=3D0) or
     (Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]&gt;D) then
  Begin
   Conn[Ord(P1)-Ord('A')+1,Ord(P2)-Ord('A')+1]:=3DD;
   Conn[Ord(P2)-Ord('A')+1,Ord(P1)-Ord('A')+1]:=3DD;
  End;
 End;
 Close(TF);
 For X:=3D1 to 58 do
  Dist[X]:=3D2147483647;                  {Set all distances to =
infinity}
 Dist[Ord('Z')-Ord('A')+1]:=3D0;          {Set distance from barn to =
barn to 0}
End;

Procedure Solve;
Var X,P,D:LongInt;                      {P =3D pasture and D =3D =
distance}

Begin
 Repeat
  P:=3D0;
  D:=3D2147483647;
  For X:=3D1 to 58 do                     {Find nearest pasture not
visited yet}
   If Not Vis[X] and (Dist[X]&lt;D) then
   Begin
    P:=3DX;
    D:=3DDist[X];
   End;
  If (P&lt;&gt;0) then
  Begin
   Vis[P]:=3DTrue;                        {If there is one mark it
visited}
   For X:=3D1 to 58 do                    {And update all distances}
    If (Conn[P,X]&lt;&gt;0) and (Dist[X]&gt;Dist[P]+Conn[P,X]) then
     Dist[X]:=3DDist[P]+Conn[P,X];
  End;
 Until (P=3D0);                {Until no reachable and unvisited =
pastures
left}
End;

Procedure Save;
Var TF  :Text;
    X,BD:LongInt;                       {BD =3D best distance}
    BP  :Char;                          {BP =3D best pasture}

Begin
 BD:=3D2147483647;
 For X:=3D1 to 25 do                      {Find neares pasture}
  If (Dist[X]&lt;BD) then
  Begin
   BD:=3DDist[X];
   BP:=3DChr(Ord('A')+X-1);
  End;
 Assign(TF,'comehome.out');
 Rewrite(TF);
 Writeln(TF,BP,' ',BD);                 {Write outcome to disk}
 Close(TF);
End;

Begin
 Load;
 Solve;
 Save;
End.</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
href=3D"http://hi.baidu.com/leokan/modify/blog/13f45c0f0799b32e6159f379">=
=B1=E0=BC=AD</A> |=20
<A onclick=3D"return blogdel('blogdelform')"=20
href=3D"http://hi.baidu.com/leokan/blog/item/13f45c0f0799b32e6159f379.htm=
l#">=C9=BE=B3=FD</A>=20

<FORM id=3Dblogdelform style=3D"DISPLAY: none" name=3Dblogdelform=20
action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D1 =
name=3Dct><INPUT=20
type=3Dhidden value=3D3 name=3Dcm><INPUT type=3Dhidden =
value=3D13f45c0f0799b32e6159f379=20
name=3DspBlogID><INPUT type=3Dhidden =
value=3Dhttp://hi.baidu.com/leokan/blog=20
name=3DspRefURL></FORM>
<SCRIPT language=3Djavascript>
	<!--

function blogdel(str)
{
	var pop=3Dnew Popup({ =
contentType:3,isReloadOnClose:false,width:340,height:80});
	pop.setContent("title","=C9=BE=B3=FD=CE=C4=D5=C2");
	=
pop.setContent("confirmCon","=C4=FA=C8=B7=B6=A8=D2=AA=B3=B9=B5=D7=C9=BE=B3=
=FD=D5=E2=C6=AA=CE=C4=D5=C2=BC=B0=C6=E4=CB=F9=D3=D0=C6=C0=C2=DB=C2=F0=A3=BF=
");
	pop.setContent("callBack",delCallback);
	pop.setContent("parameter",{fid:str,popup:pop});
	pop.build();
	pop.show();
	return false;
}

function delCallback(para)
{
	var o_pop=3Dpara["popup"];
	o_pop.config.contentType=3D1;
	o_pop.setContent("contentUrl","");
	o_pop.reBuild();
	G(para["fid"]).target=3Do_pop.iframeIdName;
	eval("document."+para["fid"]).submit();
}
	//-->
	</SCRIPT>
| <A =
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/13f45c0f0799b32e6159f379.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 2.4.1 The Tamworth Two =CC=E2=BD=E2', 'USACO =
2.4.1 The Tamworth Two =
...','/leokan/blog/item/5e941cdf139de9176227984a.html'];
var post =3D [true,'USACO 2.4.3 Cow Tours =CC=E2=BD=E2','USACO 2.4.3 Cow =
Tours =CC=E2=BD=E2', '/leokan/blog/item/6c8001d76b8cf3d9a044df08.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' +  post[2] + '</a>');
	}
	document.write('</div>');
}
/*]]>*/
</SCRIPT>
 </DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
	TEXT-DECORATION: none
}
</STYLE>

<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
    if(arg.length <=3D 1) return false;
    var hasMore =3D arg[0];
    var D=3Dfunction(A,B){A[A.length]=3DB;}
    if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);

    var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
    D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
    for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
        D(html, '<tr>');
        D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
        D(html, new Array(10).join('\u3000'));
        D(html, '</td>');
        if(arg[i + 1][0] !=3D "")
            D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
        else
            D(html, '<td>&nbsp;</td><td>&nbsp;</td>');
        D(html, '</tr>');
    }
    if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%202%2E4%2E4=
%20Bessie%20Come%20Home%20%CC%E2%BD%E2&item=3D13f45c0f0799b32e6159f379">=B8=
=FC=B6=E0&gt;&gt;</a></td></tr>');
    D(html, '</table></div><div class=3D"line">&nbsp;</div>');

    var div =3D document.getElementById('in_related_tmp');
    if(div){
        div.innerHTML =3D html.join('');
        while(div.firstChild){
            div.parentNode.insertBefore(div.firstChild, div);
        }
        div.parentNode.removeChild(div);
    }
}

if(RelatedDocData =3D=3D -1){	// not supported xhr
    var script =3D document.createElement('script');
    script.type =3D 'text/javascript';
    script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%202%2E4%2E4%20Bessie%20Come%20Home%20%=
CC%E2%BD%E2&item=3D13f45c0f0799b32e6159f379&t=3D' + new =
Date().getTime();
    document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
	GetAndEval =3D true;
}else{
	eval(RelatedDocData);
}

/*]]>*/
</SCRIPT>

<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>

	var g_spAnnony=3Dfalse;


var g_read=3D[

{}
];
g_read.length=3Dg_read.length-1;

var _rh1=3D"";
var _rh2=3D"";

function wrreader(){
	_rh1 +=3D '<table width=3D"100%" ><tr>';
	_rh2+=3D'<tr>';
	if(g_spAnnony){
		_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
		_rh2+=3D'<td>&nbsp;</td>';
		if(g_read.length>0){
			_rh1+=3D'<td align=3D"left" width=3D"12%">';
		}else{
			_rh1+=3D'<td align=3D"left" width=3D"100%">';
		}
		_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
		_rh2+=3D'<td>&nbsp;</td>'
	}
	if(g_read.length=3D=3D0){
		if(!g_spAnnony){
			_rh1+=3D'<td align=3Dleft =
width=3D"100%">=D7=EE=BD=FC=BB=B9=C3=BB=D3=D0=B5=C7=C2=BC=D3=C3=BB=A7=BF=B4=
=B9=FD=D5=E2=C6=AA=CE=C4=D5=C2=A1=AD=A1=AD</td>';
			_rh2+=3D'<td>&nbsp;</td>';
		}
	}else{
		for(i=3D0,len=3Dg_read.length;i<len;i++){
			_rh1+=3D'<td align=3D"center" valign=3D"bottom" width=3D"10%" =
class=3D"user"><a href=3D"/'+g_read[i][0]+'" target=3D"_blank"><img =
border=3D"0" =
src=3D"http://himg.baidu.com/sys/portraitn/item/'+g_read[i][1]+'.jpg"></a=
></td>';
			_rh2+=3D'<td align=3D"center" valign=3D"top" class=3D"user"><a =
href=3D"/'+g_read[i][0]+'" target=3D"_blank">'+g_read[i][2]+'</a></td>';
		}
	}
	_rh1+=3D'<td width=3D"100%"></td></tr>';
	_rh2+=3D'<td></td></tr></table>';
	document.write(_rh1+_rh2);
}

wrreader();
</SCRIPT>
</DIV>
<DIV class=3Dline></DIV>
<SCRIPT language=3DJavaScript>
allkey=3Dallkey+"142d077b0bb076f40bd18714_13f45c0f0799b32e6159f379_";
</SCRIPT>

<DIV id=3Din_comment><A name=3Dcomment></A>
<DIV class=3Dtit>=CD=F8=D3=D1=C6=C0=C2=DB=A3=BA</DIV>
<SCRIPT>
function writecmt(type,id,cmtname,cmturl,portraitId){
	var html1=3D"";

	if(type=3D=3D1){
			html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'><img  border=3D'0' =
src=3D'http://himg.baidu.com/sys/portraitn/item/"+portraitId+".jpg'><br>"=
+cmtname+"</a>";
	}else{
		if(cmtname=3D=3D"" || cmtname=3D=3D"=C4=E4=C3=FB=CD=F8=D3=D1"){
			if(cmturl=3D=3D""){
				html1=3D"<a name=3D'"+id+"'>=C4=E4=C3=FB=CD=F8=D3=D1</a>";
			}else{
				html1=3D"<a name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a>";
			}
		}else{
			if(cmturl=3D=3D""){
				html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"'>"+cmtname+"</a></div>";
			}else{
				html1=3D"<div class=3D'f14' style=3D'display:inline'>=CD=F8=D3=D1:<a =
name=3D'"+id+"' href=3D'"+cmturl+"' target=3D'_blank' =
title=3D'"+cmturl+"'>"+cmtname+"</a></div>";
			}
		}
	}
	document.write(html1);
}

</SCRIPT>

<DIV id=3Dpage></DIV></DIV>
<DIV id=3Din_send><A name=3Dsend></A>
<FORM id=3DpopFormSubmit name=3Dform1 onsubmit=3D"return checkcmtform()" =

action=3D/leokan/commit method=3Dpost><INPUT type=3Dhidden value=3D8 =
name=3Dct> <INPUT=20
type=3Dhidden value=3D1 name=3Dcm> <INPUT type=3Dhidden =
value=3D13f45c0f0799b32e6159f379=20
name=3DspBlogID>
<SCRIPT language=3DJavaScript>
	document.write("<input type=3D'hidden' name=3D'spRefURL' =
value=3D'"+window.location.href+"'>");
</SCRIPT>
=20
<DIV class=3Dtit>=B7=A2=B1=ED=C6=C0=C2=DB=A3=BA</DIV>
<TABLE cellSpacing=3D5 cellPadding=3D0 width=3D620 border=3D0>
  <TBODY>
  <TR>
    <TD class=3Df14>=D0=D5=A1=A1=C3=FB=A3=BA</TD>