• API
• FAQ
• Tools
• Trends
• Archive
daily pastebin goal
29%
SHARE
TWEET

# Dijkstra

a guest Jun 19th, 2017 61 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);
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
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
Top