Pagini recente » Atasamentele paginii Profil ev1licious | Cod sursa (job #1210504)
program p257d;
type lista=^celula;
celula=record
muchie,nod:longint;
ruta:byte;
next:lista;
end;
const c=18446744073709551615;
var n,m,k,i,x,y,z,current,heapsize:longint;
a:array [1..100000] of lista;
r:lista;
drum,heap,pos,nr:array [1..100000]of qword;
rut: array [1..100000] of byte;
bufin,bufout:array[1..100000]of byte;
procedure up(x:longint);
var w:longint;
begin
if x>1 then
if drum[heap[x div 2]]>drum[heap[x]] then
begin
w:=heap[x div 2];
heap[x div 2]:=heap[x];
heap[x]:=w;
pos[heap[x div 2]]:=x div 2;
pos[heap[x]]:=x;
up(x div 2);
end;
end;
procedure heapify(x:longint);
var w,min:longint;
begin
min:=x;
if 2*x<=heapsize then
if drum[heap[2*x]]<drum[heap[min]] then min:=2*x;
if 2*x+1<=heapsize then
if drum[heap[2*x+1]]<drum[heap[min]] then min:=2*x+1;
if min<>x then
begin
w:=heap[min];
heap[min]:=heap[x];
heap[x]:=w;
pos[heap[min]]:=min;
pos[heap[x]]:=x;
heapify(min);
end;
end;
begin
assign(input,'dijkstra.in');
reset(input);
settextbuf(input,bufin);
assign(output,'dijkstra.out');
rewrite(output);
settextbuf(output,bufout);
readln(n,m);
for i:=1 to m do
begin
readln(x,y,z);
new(r);
r^.muchie:=z;
r^.nod:=y;
r^.ruta:=0;
r^.next:=a[x];
a[x]:=r;
{ new(r);
r^.muchie:=z;
r^.nod:=x;
r^.ruta:=0;
r^.next:=a[y];
a[y]:=r; }
end;
for i:=1 to k do
begin
readln(y,z);
new(r);
r^.muchie:=z;
r^.nod:=y;
r^.ruta:=1;
r^.next:=a[1];
a[1]:=r;
end;
for i:=2 to n do drum[i]:=c;
heap[1]:=1;
pos[1]:=1;
heapsize:=1;
while heapsize>0 do
begin
current:=heap[1];
heap[1]:=heap[heapsize];
dec(heapsize);
r:=a[current];
while r<>nil do
begin
if drum[r^.nod]=c then
begin
inc(heapsize);
heap[heapsize]:=r^.nod;
pos[r^.nod]:=heapsize;
end;
if (drum[r^.nod]=c)or (drum[r^.nod]>drum[current]+r^.muchie) then
begin
drum[r^.nod]:=drum[current]+r^.muchie;
rut[r^.nod]:=r^.ruta;
end;
if drum[r^.nod]=drum[current]+r^.muchie then
if r^.ruta=0 then rut[r^.nod]:=0;
up(pos[r^.nod]);
r:=r^.next;
end;
end;
for i:=2 to n do if drum[i]=c then write(0,' ') else write(drum[i],' ');
{ for i:=2 to n do if rut[i]=1 then dec(k);
writeln(k); }
close(output);
end.