ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1072. Routing

Why I get WA? Pelase, help me!!!!!!!
Posted by Revenger and NSC 22 Dec 2001 14:05
There is my solution:

Program t1072;

Const MaxN=100;
      MaxK=10;

Type TCPIP=record IP,Mask :array[1..4]of longint end;

Var  N,K,i,j,count :longint;
     S             :string[255];
     Route         :array[1..MaxN,1..MaxN]of boolean;
     MinWay        :array[1..MaxN]of longint;
     PredWay       :array[1..MaxN]of longint;
     Comp1,Comp2   :longint;
     Next          :longint;
     Way           :array[1..MaxN]of longint;
     ex            :boolean;
     net           :array[1..MaxN]of record
                      K      :longint;
                      TCP_IP :array[1..MaxK]of TCPIP;
                    end;

Function SameNet(_IP1,_IP2:TCPIP):boolean;
var r1,r2,r3,r4 :boolean;
 begin
  r1:= (_IP1.IP[1] AND _IP1.Mask[1]) = (_IP2.IP[1] AND _IP2.Mask[1]);
  r2:= (_IP1.IP[2] AND _IP1.Mask[2]) = (_IP2.IP[2] AND _IP2.Mask[2]);
  r3:= (_IP1.IP[3] AND _IP1.Mask[3]) = (_IP2.IP[3] AND _IP2.Mask[3]);
  r4:= (_IP1.IP[4] AND _IP1.Mask[4]) = (_IP2.IP[4] AND _IP2.Mask[4]);
  SameNet:= r1 AND r2 AND r3 AND r4 ;
 end;

Function InSameNet(comp1,comp2 :longint):boolean;
var i1,i2     :longint;
    ok        :boolean;
 begin
  for i1:=1 to net[comp1].K do
   for i2:=1 to net[comp2].K do
    if SameNet(net[comp1].TCP_IP[i1],net[comp2].TCP_IP[i2]) then begin
     InSameNet:=true;
     exit;
    end;
  InSameNet:=false;
 end;

Procedure MakeTCP(S:string;Var D :TCPIP);
var n1,n2,n3,n4    :longint;
    t1,t2,t3,t4    :longint;
    CurNum         :string[255];
    i,j,code       :longint;
 begin
  j:=1;
  while S[j]=' ' do j:=j+1;
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,n1,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,n2,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,n3,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>' ' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,n4,code);
  while S[j]=' ' do j:=j+1;
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,t1,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,t2,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>'.' then CurNum:=CurNum+S[i] else break;
  j:=i+1;
  val(CurNum,t3,code);
  CurNum:='';
  for i:=j to length(S) do
   if S[i]<>' ' then CurNum:=CurNum+S[i] else break;
  val(CurNum,t4,code);
  D.IP[1]:=n1;
  D.IP[2]:=n2;
  D.IP[3]:=n3;
  D.IP[4]:=n4;
  D.Mask[1]:=t1;
  D.Mask[2]:=t2;
  D.Mask[3]:=t3;
  D.Mask[4]:=t4;
 end;

begin
Assign(input,'1072.in');ReSet(input);
for i:=1 to MaxN do
 for j:=1 to MaxN do
  Route[i,j]:=false;
Readln(N);
for i:=1 to N do begin
 Readln(K);
 net[i].K:=K;
 for j:=1 to K do begin
   Readln(S);
   MakeTCP(S,net[i].TCP_IP[j]);
  end;
end;
Read(Comp1,Comp2);
if comp1=comp2 then begin
 Writeln('YES');
 Writeln(comp1);
 Halt(0);
end;
for i:=1 to N do
 for j:=1 to N do
  if i<>j then Route[i,j]:=InSameNet(i,j);
for i:=1 to MaxN do MinWay[i]:=-1;
for i:=1 to MaxN do PredWay[i]:=0;
count:=0;
MinWay[comp1]:=1;
repeat
 ex:=true;
 count:=count+1;
 for i:=1 to N do
  if MinWay[i]=count then
   for j:=1 to N do
    if Route[i,j] then
     if MinWay[j]=-1 then begin
      MinWay[j]:=count+1;
      PredWay[j]:=i;
      ex:=false;
     end;
until ex;
if MinWay[comp2]=-1 then writeln('NO') else begin
 Next:=comp2;
 j:=MinWay[comp2]+1;
 while Next<>0 do begin
  j:=j-1;
  Way[j]:=Next;
  Next:=PredWay[Next];
 end;
 writeln('YES');
 i:=0;
 for i:=1 to MinWay[comp2]-1 do write(Way[i],' ')
YES --> Yes, NO --> No
Posted by abc 22 Dec 2001 14:43
Re: What does it mean?
Posted by Revenger and NSC 22 Dec 2001 19:38
>
Change ES of YES to es and O of NO to o (upper case to lower case)
Posted by Timus Observer 22 Dec 2001 20:43
> >
Thank you!
Posted by Revenger and NSC 22 Dec 2001 21:58
> > >
Thank you!
Posted by <<<__WOLF__>>> 30 Jun 2007 14:27
>>>>>>>