fork download
copy 
  1. program micammino;
  2. const MAX = 200000;
  3.       QSIZE = 400000;
  4. var N, M,a,b,c,h,i: int64;
  5.     graph : array[0..MAX-1] of array of int64;
  6.     peso : array[0..MAX-1] of array of int64;
  7.     gsize, gcapa: array[0..MAX-1] of int64;
  8.     visited : array[0..MAX-1] of boolean;
  9.     D, S,E,P : array[0..MAX-1] of int64;
  10.     q1, q2 : array[0..QSIZE-1] of int64;
  11.  
  12.  
  13. procedure mincammino(partenza:int64; arrivo:int64; var D : array of int64); 
  14.  var qhead, qcount, first, second, i, j : int64;
  15.  
  16.  begin
  17.  
  18.    for h:=0 to N-1 do
  19.        begin
  20.         setlength(graph[h], 1); 
  21.         setlength(peso[h], 1);
  22.         gsize[h] := 0;
  23.         gcapa[h] := 1;
  24.         D[h] := maxlongint;
  25.       end;
  26.       q1[0] := partenza; q2[0] := 0;
  27.    qhead := 0; qcount := 1;
  28.    for i:=0 to N-1 do visited[i] := False;
  29.    while qcount > 0 do
  30.        begin
  31.          first := q1[qhead];
  32.          second := q2[qhead];
  33.          inc(qhead);
  34.          if qhead = QSIZE then
  35.          qhead := 0;
  36.          dec(qcount);
  37.          if (visited[first]=true) then
  38.                                     begin
  39.                                       if second<D[first] then D[first]:=second
  40.                                                             else continue;
  41.                                     end;                                           
  42.          visited[first] := True;
  43.          D[first] := second;
  44.          for j:=0 to gsize[first]-1 do
  45.                  begin
  46.                   q1[(qhead + qcount) mod QSIZE] := graph[first][j];
  47.                   q2[(qhead + qcount) mod QSIZE] := second + peso[first][j];
  48.                   inc(qcount);
  49.                 end;
  50.        end;
  51.     for h:=0 to M-1 do
  52.       begin
  53.        a := S[h]; b := E[h]; c:=P[h];
  54.        if gsize[a] = gcapa[a] then
  55.             begin
  56.               gcapa[a] := gcapa[a] shl 1;
  57.               setlength(graph[a], gcapa[a]);
  58.               setlength(peso[a], gcapa[a]);
  59.             end;
  60.        graph[a][gsize[a]] := b;
  61.        peso[a][gsize[a]] := c;
  62.        inc(gsize[a]);
  63.      end;  
  64.  end;
  65. begin
  66.  (*assign(input,  'input.txt');  reset(input);
  67.   assign(output, 'output.txt'); rewrite(output);*)
  68.   readln(N,M); 
  69.   for h:=0 to M-1 do readln(S[h],E[h],P[h]);
  70.   mincammino(0,N-1,D);
  71.   for i:= 0 to N-1 do  begin if D[i]=maxlongint then D[i]:=-1;  write(D[i],' '); end;
  72.  
  73. end.
  74.  
  75.  
  76.  
Success #stdin #stdout 0.01s 14612KB
comments (?)
stdin
copy 
4 5
0 1 1
0 2 2
1 3 1
2 1 3
2 3 5
stdout
copy 
0 -1 -1 -1
https://ideone.com/06XUqQ
language:
Pascal (fpc 3.0.4)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!