10308 - Roads in the North

[Joe Smith]

Am I wrong in assuming the graph is a tree? I interpret the statement "there is only one route from a village to a village that does not pass through some other village twice" as meaning there are no cycles, and it says there's only 1 component. If this is right then it's easy, just dfs, but I'm getting WA.

[shahriar_manzoor]

There can be inputs with zero cities!!!

[Joe Smith]

There can be inputs with zero cities!!!

Oops, I guess I can't read.

Thanks!

[Revenger]

I use DFS. But Can anybody say why this program get WA?

[pascal]Program p10308;

Const MaxN = 10000;
p1 = 5000;
p2 = 500;

Type Comp = Integer;

Var Map : Array[1..MaxN]of Record A,B : Integer; L : Comp; End;
list,p : Array[0..MaxN]of Integer;
Road,R : Array[1..MaxN]of Comp;
i,N,M : Integer;
a,b,j : Integer;
lmin : Integer;
min,mid : Comp;
l,max : Comp;
tt : byte;

Function GetLast(E : Integer) : Integer;
Var Use : Array[1..MaxN]of byte;
i,j : Integer;
ok : Byte;
begin
FillChar(Use,SizeOf(Use),0);
Use[E]:=1;
Road[E]:=0;
l:=0;
GetLast:=E;
While True Do begin
ok:=1;
for i:=1 to M do
if (Use[Map.A]=1)and(Use[Map.B]=0) then begin
ok:=0;
Use[Map.B]:=1;
Road[Map.B]:=Road[Map.A]+Map.L;
if Road[Map.B]>l then begin
l:=Road[Map.B];
GetLast:=Map.B;
end;
end else
if (Use[Map.A]=0)and(Use[Map[i].B]=1) then begin
ok:=0;
Use[Map[i].A]:=1;
Road[Map[i].A]:=Road[Map[i].B]+Map[i].L;
if Road[Map[i].A]>l then begin
l:=Road[Map[i].A];
GetLast:=Map[i].A;
end;
end;
if ok=1 then Break;
end;
end;

begin
While Not Eof(InPut) Do begin
N:=0;
M:=0;
i:=1;
While True do begin
if (Eof(InPut))or(Eoln(InPut)) then Break;
Readln(a,b,l);
if a>N then N:=a;
if b>N then N:=b;
Map[i].A:=a;
Map[i].B:=b;
Map[i].L:=l;
i:=i+1;
M:=M+1;
if (Eof(InPut))or(Eoln(InPut)) then Break;
end;
if Eoln(InPut) then Readln;
if N=0 then Readln;
i:=GetLast(1);
GetLast(i);
Writeln(l:0);
end;
end.[/pascal]

[Rivaldo]

It says "The villages are numbered from 1."
Does it mean the villages are numberd 1, 2, 3, 4, ..., n, when the number of village is n.

[Maxim]

What like looks input case when there are zero villages? Is it a blank line, or it consists of line with 0 for village i or j? Please, help. I've solved it and tested it on my computer, but when I send it, it gets Runtime Error (Invalid memory reference). I decrease index of each vilage after scaning it. Upper bound sure doesn't make any trouble.

[scythe]

Uhm.. yeah

[ithamar]

I has not solved this problem but from the problem statement i cant asure that the cities are numered sequentially 1, 2, ..., n. Maybe some data set could be 1, 2, 6, 12, maybe not. But the problem statement leave the second posibility open so you shuld take care of.

[scythe]

I got ac, but my source code works for that kind of tests.
I'm sorry, I guess the cities could be numbered in a non-compact manner. (I misunderstood your question)

[little joey]

There can be inputs with zero cities!!!

Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.

It's a pitty to see a perfect problem spoiled by this kind of nonsense.

(Shahriar, I know you're not the problemsetter, just the messenger; this is not a personal attack )

[Per]

Well, I know we're required to answer '0' in this case, but it makes no sense. The distance between two non-existent cities is zero? That's only because one particular implementation of an algorithm to solve this problem would answer '0'. Mathematical sense would give 'undefined'.

It would also be consistent with mathematical sense (more so than letting it be undefined, in my opinion) to define the distance as negative infinity in such cases (cf. the degree of the zero polynomial, for example).

[Dominik Michniewski]

I use DFS() to solve this problem, but I got WA several times ...
Is any trap in this problem ?
My program outputs 0 when input has na cities. When I traverse graph in every node I remember two maximal distances from this node to any children. Sum of this values in every node is maximal distance between nodes. If I compute all nodes, I should get correct answer. Of course if graph is connected ... Am I wrong with this algorithm ? Could anyone help me ?

Best regards
DM

[artem]

Dominik your algorithm is right (I got AC with same algorithm).
In this algorithm only one intersting place:

Code: Select all

DFS(...){
 int max1=0,max2=0,.....; 
 ......  // cycle
 t=DFS(.....);
 if (t > max1){
 max2=max1;
 max1=t;
 }
 else  if (t > max2) max2=t;
 ....... // end cycle
 if (max1+max2 > max) max=max1+max2;
 return max1;
}

where max - is our answer and max1,max2 - two maximal distances from this node ( max1 >= max2)

[daveon]

INPUT:

Code: Select all

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
(blank line)
(blank line)
(blank line)
(blank line)
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

OUTPUT:

Code: Select all

22
0
22

[helloneo]

INPUT:

Code: Select all

5 1 6
1 4 5
6 3 9
2 6 8
6 1 7
(blank line)
(blank line)
(blank line)
(blank line)
5 1 6
1 4 5
6 3 9
2 6 8
6 1 7

OUTPUT:

Code: Select all

22
0
22

Why is it like that..?
Problem statement say
Two consecutive sets are separated by a blank line