Cod sursa(job #1670396)

Utilizator laura.calimanLaura Caliman laura.caliman Data 31 martie 2016 18:12:25
Problema Algoritmul lui Dijkstra Scor 10
Compilator fpc Status done
Runda Arhiva educationala Marime 1.84 kb
var
  a, b, c, d: array[1..250000] of longint;
  n, m, i, j, k: longint;
  t: boolean;

procedure sw(var a, b: longint);
var
  c: longint;
begin
  c := a;
  a := b;
  b := c;
end;

procedure qs(st, dr: longint);
var
  i, j, k: longint;
begin
  i := st;
  j := dr;
  k := a[(i + j) div 2];
  while i < j do 
  begin
    while a[i] < k do inc(i);
    while a[j] > k do dec(j);
    if i <= j then begin
      if a[i] = a[j] then begin
        if b[i] > b[j] then begin
          sw(b[i], b[j]);
          sw(c[i], c[j]);
        end
      end else begin
        sw(a[i], a[j]);
        sw(b[i], b[j]);
        sw(c[i], c[j]);
      end;
      inc(i);
      dec(j);
    end;
  end;
  if st < j then qs(st, j);
  if i < dr then qs(i, dr);
end;

begin
  assign(input, 'dijkstra.in');
  assign(output, 'dijkstra.out');
  reset(input);
  rewrite(output);
  read(n, m);
  for i := 1 to m do 
  begin
    read(a[i], b[i], c[i]);
    //    if b[i]<a[i] then sw(a[i],b[i]);
  end;
  d[1]:=0;
  for i:=2 to n do d[i]:=-1;
  //  qs(1,m);
  //  for i:=1 to m do
  //    writeln(a[i],' ',b[i],' ',c[i]);
  t := true;
  while t do 
  begin
    t := false;
    for i := 1 to m do 
    begin
      if d[b[i]] = -1 then begin
        t := true;
        d[b[i]] := d[a[i]] + c[i];
        //      e[a[i]]:=b[i];
      end;
      if (d[b[i]] > d[a[i]] + c[i]) then begin
        //      j:=d[b[i]]-d[a[i]]-c[i];
        t := true;
        d[b[i]] := d[a[i]] + c[i];
        //      e[a[i]]:=b[i];
        //      k:=b[i];
        //      while e[k]<>0 do begin
        //        dec(d[e[k]],j);
        //        k:=e[k];
        //      end;
      end;
    end;
    //    for j:=1 to m do
    //      write(d[j],' ');
    //    writeln;
  end;
  for i := 2 to n do if d[i]=-1 then write(0,' ') else write(d[i], ' ');
end.