Тема: Поиск самых отдалённых вершин в дереве
Задано кол-во вершин в графе,потом N-1 строк по 3 числа(описание рёбер).
Требуется найти расстояние между двумя самыми отдалёнными вершинами в дереве.
Вот мой код,который не прходит все тесты из-за Time-limita в 2 секунды:
Var root:array[0..1001] of longint;
a,aa:array[0..1001,0..1001] of longint;
b:array[0..1001] of boolean;
d,i,j,n,m,z,x,y,num,u,max,min:longint;
BEgin
Assign(input,'input.txt');
Reset(input);
Read(n);
for i:=1 to n do
begin
for j:=1 to n do
a[i,j]:=0;
end;
for i:=1 to n-1 do
begin
Read(x,y,z);
a[x,y]:=z;
a[y,x]:=z;
inc(root[x]);
inc(root[y]);
end;
max:=0;
for u:=1 to n do
if root[u]=1 then begin
d:=u;
fillchar(b,sizeof(b),true);
for i:=1 to n do
begin
num:=d;
min:=maxlongint;
for j:=1 to n do
if (a[d,j]>0)and(b[j])and(a[d,j]<min) then begin
num:=j;
min:=a[d,j];
end;
b[num]:=false;
for j:=1 to n do
if (a[num,j]>0)and((a[num,j]+a[d,num]<a[d,j])or(a[d,j]=0)) then a[d,j]:=a[d,num]+a[num,j];
end;
for i:=1 to n do
if (a[d,i]>max)and(i<>d) then max:=a[d,i];
end;
Writeln(max);
Close(input);
End.Я брал вершины которые связаны лишь одним ребром с остальными и искал самые отдалённые вершины от них через алгоритм дейкстры.
