SHARE
TWEET

Dijkstra

a guest Jun 19th, 2017 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. type
  2.   vertix = record
  3.     v, w: Integer;
  4.   end;
  5.  
  6. var
  7.   g: array of array of vertix;
  8.   d: array of Integer;
  9.   vis: array of Boolean;
  10.   N, M, S, i, v, u, w, j: Integer;
  11.  
  12. procedure AddElem(v, u, w: Integer);
  13. begin
  14.   SetLength(g[v], Length(g[v]) + 1);
  15.   g[v, high(g[v])].v := u;
  16.   g[v, high(g[v])].w := w;
  17. end;
  18.  
  19. begin
  20.   Assign(input, 'input.txt'); Reset(input);
  21.   Assign(output, 'output.txt'); Rewrite(output);
  22.   Readln(N, M, S);
  23.   SetLength(d, N);
  24.   SetLength(vis, N);
  25.   for i := 0 to N - 1 do
  26.     d[i] := high(Integer);
  27.   d[S - 1] := 0;
  28.   SetLength(g, n);
  29.   for i := 0 to M - 1 do begin
  30.     Readln(v, u, w);
  31.     AddElem(v - 1, u - 1, w);
  32.   end;
  33.   for i := 0 to N - 1 do begin
  34.     v := -1;
  35.     for j := 0 to N - 1 do
  36.       if (not vis[j]) and ((v = -1) or (d[j] < d[v])) then
  37.         v := j;
  38.     if d[v] = high(Integer) then break;
  39.     vis[v] := true;
  40.     for j := 0 to Length(g[v]) - 1 do begin
  41.       u := g[v, j].v;
  42.       w := g[v, j].w;
  43.       if (d[v] + w) < d[u] then
  44.         d[u] := d[v] + w;
  45.     end;
  46.   end;
  47.   for i := 0 to N - 1 do
  48.     if d[i] = high(Integer) then
  49.       write('-1 ')
  50.     else
  51.       write(d[i], ' ');
  52.   Close(input); Close(output);
  53. end.
RAW Paste Data
Pastebin PRO Summer Special!
Get 40% OFF on Pastebin PRO accounts!
Top