PCYCLE - Thám hiểm mê cung

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=210;
      oo=1000000000;
var n,m,s,sum:longint;
    a,b:array[1..maxn,1..maxn] of longint;
    re,f:array[1..maxn*maxn] of longint;

procedure rf;
var i,x,y:longint;
begin
     read(n,m);
     for x:=1 to n do
         for y:=1 to n do
             a[x,y]:=-oo;
     for i:=1 to m do
     begin
          read(x,y,a[x,y]);
          a[y,x]:=a[x,y];
          sum:=sum+a[x,y];
     end;
     b:=a;
end;

procedure work;
var i,pos,min:longint;
begin
     min:=oo+oo;
     for i:=2 to m+1 do
     begin
          f[i]:=f[i-1]+b[re[i],re[i-1]];
          if f[i]<min then
          begin
               min:=f[i];
               pos:=i;
          end;
     end;
     if pos=m+1 then pos:=1;
     for i:=pos to m do write(re[i],' ');
     for i:=1 to pos do write(re[i],' ');
end;

procedure try(i,x:longint);
var y,t:longint;
begin
     if (i>m+1) and (re[m+1]=re[1]) then
     begin
          work;
          close(input); close(output);
          halt;
     end;
     for y:=1 to n do
         if a[x,y]<>-oo then
         begin
              re[i]:=y; t:=a[x,y];
              a[x,y]:=-oo; a[y,x]:=-oo;
              try(i+1,y);
              a[y,x]:=t; a[x,y]:=t;
         end;
end;

procedure pr;
var i:longint;
begin
     if sum<0 then writeln(-1)
     else
     begin
          re[1]:=1;
          try(2,1);
          writeln(-1);
     end;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     rf;
     pr;
     close(input); close(output);
end.

Download