, : -, , -, N-1 (N - ).
.
procedure step(v,k: byte; r: longint);var j: byte;begin if r < min then if k = N-1 then min:= r else for j:= 1 to N do if (sm[v,j]<>0)and(mark[j]=0) then begin mark[j]:= 1; step(j,k+1,r+sm[v,j]); mark[j]:= 0 end;end;begin... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; for i:= 1 to N do begin mark[i]:=1; step(i,1,0); mark[i]:=0; end; writeln(min);...end.
, , .
-
, " " , - . "" , "" - . t .
sm, mark . , " " , -, mark , - :
procedure rasst(v: byte; r: longint);var i: byte;begin if v = t then if r< min then min:= r else else for i:= 1 to N do if (mark[i]=0)and(sm[v,i]<>0) then begin mark[i]:=1; rasst(i,r+sm[v,i]); mark[i]:=0 endend;begin... for i:= 1 to N do mark[i]:= 0; min:= MaxLongInt; mark[s]:= 1; rasst(s,0); mark[s]:= 0;...end.
, , -, , , s t, .
dist s . MaxLongInt, "". , .
done , , ( ) .
last .
, . N-1 .
|
|
|
s s, , 0. , - . :
dist[s]:= 0; done[s]:= true; last:= s;N-1 :
, last, :
dist[x]:= min(dist[x], dist[last]+ sm[last,x]);dist: last;
done.
dist[s]:= 0; done[s]:= true; last:= s;for i:= 1 to N-1 do begin for x:= 1 to N do if (sm[last,x]<>0)and(not done[x]) then dist[x]:= min(dist[x],dist[last]+ sm[last,x]); min_dist:= MaxLongInt; for x:= 1 to N do if (not done[x])and(min_dist>dist[x]) then begin min_dist:= dist[x]; last:= x; end; done[last]:= true; end.
: :
― :
― -;
― .
― :
― -;
― .
:
1. .
2. .
-, , - .
