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