Тема: Нахождение минимального остова по алгоритму Прима
Написал прогу, вычисляющую длину минимального остовного дерева по алгоритму Прима, успешно сдал на школе программиста (http://acmp.ru/index.asp?main=task&id_task=142). Но там ограничение по вершинам 100, по рёбрам 6000, по весу 30000 и не нужно проверять граф на связность. Мне же нужно сдать задачу с вершинами до 300, рёбрами до 50000, весом до 10000 и проверкой на связность. Вроде всё нормально, но выдаёт неправильный ответ на 2 тесте, не пойму почему!
const maxN=300;
var f,f1 :text;
d,from :array[1..maxN] of int64;
mark :array[1..maxN] of boolean;
a :array[1..maxN,1..maxN] of int64;
n,m,s,k,min,r :int64;
i,u,v :integer;
begin
reset(f,'spantree.in');
rewrite(f1,'spantree.out');
read(f,n,m);
for i:=1 to n do
for v:=1 to n do a[i,v]:=-1;{заполнение матрицы смежности}
for i:=1 to m do begin
read(f,u,v,s);
a[u,v]:=s;
a[v,u]:=s;
end;{считана матрица}
close(f);
for i:=2 to n do d[i]:=high(int64);
while k<n do begin
min:=high(int64);
for i:=1 to n do
if (d[i]<=min) and (not mark[i]) then begin min:=d[i]; v:=i end;
{нахождение минимального ребра из не U в U}
if d[v]=high(int64) then begin write(f1,'-1'); close(f1); halt end;
if v<>1 then r:=r+a[from[v],v];{добавление ребра в ответ и в множество U}
mark[v]:=true;{помечаем v} inc(k);
for i:=1 to n do
if (not mark[i]) and (a[v,i]>-1) and (a[v,i]<d[i]) then begin
d[i]:=a[v,i];
from[i]:=v
end;{пробегаем соседей v и изменяем кратчайший путь до них из U}
end;
write(f1,r);
close(f1);
end.