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.  
  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, i, j : 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 i:=0 to N-1 do visited[i] := 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  mincamm (N,M:int64; S, E ,P : array of int64; var D : array of int64);
  47.  
  48. begin
  49. for h:=0 to N-1 do
  50.    begin
  51.      setlength(graph[h], 1); 
  52.      setlength(peso[h], 1);
  53.      gsize[h] := 0;
  54.      gcapa[h] := 1;
  55.      D[h] := maxlongint;
  56.   end;
  57.  for h:=0 to M-1 do
  58.       begin
  59.        a := S[h]; b := E[h]; c:=P[h];
  60.        if gsize[a] = gcapa[a] then
  61.             begin
  62.               gcapa[a] := gcapa[a] shl 1;
  63.               setlength(graph[a], gcapa[a]);
  64.               setlength(peso[a], gcapa[a]);
  65.             end;
  66.        graph[a][gsize[a]] := b;
  67.        peso[a][gsize[a]] := c;
  68.        inc(gsize[a]);
  69.      end;
  70.     bfs(0,N-1,D);
  71.     for i:= 0 to N-1 do   if D[i]=maxlongint then D[i]:=-1;
  72.  
  73.     end;
  74. begin
  75.    (*assign(input,  'input.txt');  reset(input);
  76.   assign(output, 'output.txt'); rewrite(output);*)
  77.   readln(N,M); 
  78.   for i:=0 to M-1 do readln(X[i],Y[i],P[i]);
  79.   mincamm(N,M,X,Y,P,D);
  80.   for i:=0 to N-1 do  write(D[i],' '); 
  81. end.
  82.  
Success #stdin #stdout 0.01s 17120KB
comments (?)
stdin
copy 
4 5
0 1 1
0 2 2
1 3 1
2 1 3
2 3 5
stdout
copy 
0 1 2 2
https://ideone.com/Dho01t
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!