fork download 
  1. program camminominimo;
  2. const MAX = 200000;
  3.       QSIZE = 600000;
  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.  
  9.     D, X,Y,P : array[0..MAX-1] of int64;
  10.  
  11.  
  12.  
  13. procedure bfs(partenza : int64;arrivo:int64; var res : array of int64); 
  14.  var qhead, qcount, first, second, j, k : int64;
  15.      q1, q2 : array[0..QSIZE-1] of int64;
  16.      visited : array[0..MAX-1] of boolean;
  17.  
  18.  begin
  19.    q1[0] := partenza; q2[0] := 0;
  20.    qhead := 0; qcount := 1;
  21.    for k:=0 to N-1 do visited[k] := False;
  22.    while qcount > 0 do
  23.        begin
  24.          first := q1[qhead];
  25.          second := q2[qhead];
  26.          inc(qhead);
  27.          if qhead = QSIZE then
  28.          qhead := 0;
  29.          dec(qcount);
  30.          if (visited[first]=true) then
  31.                                     begin
  32.                                       if second<res[first] then res[first]:=second
  33.                                                             else continue;
  34.                                     end;                                           
  35.          visited[first] := True;
  36.          res[first] := second;
  37.          for j:=0 to gsize[first]-1 do
  38.                  begin
  39.                   q1[(qhead + qcount) mod QSIZE] := graph[first][j];
  40.                   q2[(qhead + qcount) mod QSIZE] := second + peso[first][j];
  41.                   inc(qcount);
  42.                 end;
  43.        end;
  44.  end;
  45.  
  46. Procedure  mincammino (N,M:int64; S, E ,P : array of int64; var D : array of int64);
  47. var k: int64;
  48.  
  49. begin
  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.      D[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,D);
  72.     for k:= 0 to N-1 do   if D[k]=maxlongint then D[k]:=-1;
  73.  
  74.     end;
  75. begin
  76.    (*assign(input,  'input.txt');  reset(input);
  77.   assign(output, 'output.txt'); rewrite(output);*)
  78.   readln(N,M); 
  79.   for i:=0 to M-1 do readln(X[i],Y[i],P[i]);
  80.   mincammino(N,M,X,Y,P,D);
  81.   for i:=0 to N-1 do  write(D[i],' '); 
  82. end.
  83.  
Success #stdin #stdout 0.02s 17116KB
comments (?)
stdin 
2  1
1 0 1
stdout 
0 -1
https://ideone.com/nkI6h6
language:
Pascal (fpc 3.0.4)
created:
11 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!