NKCITY - Xây dựng thành phố
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program NKCITY;
Const
input = '';
output = '';
Var
c: array[1..1000,1..1000] of integer;
d: array[1..1000] of integer;
free: array[1..1000] of boolean;
n,m: integer;
Procedure LoadGraph;
Var
f: text;
i,j,u,v: integer;
Begin
Assign(f, input);
Reset(f);
Readln(f, n, m);
For u:= 1 to n do
For v:= 1 to n do
if u = v then c[u,v]:= 0 else c[u,v]:= 1000000000;
For i:= 1 to m do
Begin
Readln(f, u, v, c[u,v]);
c[v,u]:= c[u,v];
End;
Close(f);
End;
Procedure Prim;
Var
f: text;
maxlen: integer;
u,i,min,v,k: integer;
Begin
d[1]:= 0;
For i:= 2 to n do d[i]:= 1000000000;
maxlen:= 0;
FIllchar(free, sizeof(free), true);
For k:= 1 to n do
Begin
u:= 0;
min:= 1000000000;
For i:= 1 to n do
if free[i] and (d[i] < min) then
Begin
u:= i;
min:= d[i];
End;
If maxlen < min then maxlen:= min;
free[u]:= false;
For v:= 1 to n do
If free[v] and (d[v] > c[u,v])
then d[v]:= c[u,v];
End;
Assign(f, output);
Rewrite(f);
Writeln(f, maxlen);
Close(f);
End;
Begin
LoadGraph;
Prim;
End.