Cele mai bune solutii pentru problema "Drum Lung"
(ziua2, problema3)

Punctaj Maxim : 75 puncte

Solutii :
Streng Cristian - Bihor - 75 puncte
Stroe Mihai - Bucuresti - 75 puncte
Grigorescuta Catalin - Botosani- 75 puncte
Grigoras Costin - Constanta- 75 puncte
Cristoiu Catalin - Gorj - 75 puncte
Cadar Cristian - Bucuresti - 75 puncte
Comisia Centrala
Fisierele de teste

Program realizat de elevul Streng Cristian - rezultat final : premiu I - 163 puncte

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y+}
{$M 65520,0,655360}
program p3;
type
   vect=array [0..200] of byte;
   pvect=^vect;
   mat=array [1..200] of pvect;
var
   f:text;
   aj1,aj2,aj3:mat;
   c:mat;
   n:byte;
   m:word;
   p:byte;
   k:byte;
   min1,fromi,fromk,i,j,ii,jj,im,jm:byte;
   max,kk:word;
   dm:longint;
   e1,e2:boolean;
   dr:array [1..200] of byte;
   fost:array [1..200] of boolean;
procedure reconstituie;
var
   curi,i:byte;
   kkk:byte;
   cc:byte;
begin
  curi:=ii;
  kkk:=kk;
  cc:=0;
  repeat
    inc (cc);
    dr[cc]:=curi;
    i:=curi;
    curi:=aj3[curi]^[kkk];
    dec (kkk, c[i]^[curi]);
  until kkk=0;
  write (f, k);
  for i:=cc downto 1 do
    write (f, ' ', dr[i]);
  writeln (f)
end;
begin
  for ii:=1 to 200 do
  begin
    new (c[ii]);
    new (aj1[ii]);
    new (aj2[ii]);
    new (aj3[ii]);
    for jj:=0 to 200 do
    begin
      c[ii]^[jj]:=0;
      aj1[ii]^[jj]:=0;
      aj2[ii]^[jj]:=0;
      aj3[ii]^[jj]:=0
    end
  end;
  assign (f, 'input.txt');
  reset (f);
  readln (f, n, m);
  readln (f, k, p);
  readln (f, i, j);
  for kk:=1 to m do
  begin
    readln (f, im, jm, dm);
    c[im]^[jm]:=dm;
    c[jm]^[im]:=dm
  end;
  close (f);
  aj1[i]^[0]:=i;
  for kk:=1 to p do
    for ii:=1 to n do
      for jj:=1 to n do
        if (c[ii]^[jj]<>0) and (aj1[ii]^[kk]=0) and (integer(kk)-integer(c[ii]^[jj])>=0) and
          (aj1[jj]^[kk-c[ii]^[jj]]<>0) then
          aj1[ii]^[kk]:=jj;
  aj2[j]^[0]:=j;
  for kk:=1 to p do
    for ii:=1 to n do
      for jj:=1 to n do
        if (c[ii]^[jj]<>0) and (aj2[ii]^[kk]=0) and (integer(kk)-integer(c[ii]^[jj])>=0) and
          (aj2[jj]^[kk-c[ii]^[jj]]<>0) then
          aj2[ii]^[kk]:=jj;
  aj3[k]^[0]:=k;
  for kk:=1 to p do
    for ii:=1 to n do
      for jj:=1 to n do
        if (c[ii]^[jj]<>0) and (aj3[ii]^[kk]=0) and (integer(kk)-integer(c[ii]^[jj])>=0) and
          (aj3[jj]^[kk-c[ii]^[jj]]<>0) then
          aj3[ii]^[kk]:=jj;
  for kk:=p downto 0 do
    for ii:=1 to n do
      if (aj3[ii]^[kk]<>0) then
      begin
        e1:=false;
        for jj:=0 to p-kk do
          if aj1[ii]^[jj]<>0 then
          begin
            e1:=true;
            break
          end;
        e2:=false;
        for jj:=0 to p-kk do
          if aj2[ii]^[jj]<>0 then
          begin
            e2:=true;
            break
          end;
        if e1 and e2 then
        begin
          assign (f, 'output.txt');
          rewrite (f);
          writeln (f, kk);
          flush (f);
          reconstituie;
          close (f);
          halt
        end
      end
end.

[BACK]

Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica

[BACK]

Fisierele de teste :

[BACK]