fork download
copy 
  1. program dijkstra;
  2. const MAX = 1000010;
  3.       QSIZE = 3000000;
  4. var N, M,a,b,c,h, inizio, fine : 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.  (* implementazione classica della visita in ampiezza: per implementare
  13.  * la coda in pascal facciamo uso di array circolari q1[] e q2[] in cui
  14.  * "qhead" e’ l’indice dell’elemento in testa alla coda, "qcount" e’ il
  15.  * numero di elementi presenti nella coda.
  16.  *)
  17.  
  18. procedure bfs(partenza : int64;arrivo:int64; var res : array of int64); 
  19.  var qhead, qcount, first, second, i, j : int64;
  20.  
  21.  begin
  22.    q1[0] := partenza; q2[0] := 0;
  23.    qhead := 0; qcount := 1;
  24.    for i:=0 to N-1 do visited[i] := False;
  25.    while qcount > 0 do
  26.        begin
  27.          first := q1[qhead];
  28.          second := q2[qhead];
  29.          inc(qhead);
  30.          if qhead = QSIZE then
  31.          qhead := 0;
  32.          dec(qcount);
  33.          if (visited[first]=true) then
  34.                                     begin
  35.                                       if second<res[first] then res[first]:=second
  36.                                                             else continue;
  37.                                     end;                                           
  38.          visited[first] := True;
  39.          res[first] := second;
  40.          for j:=0 to gsize[first]-1 do
  41.                  begin
  42.                   q1[(qhead + qcount) mod QSIZE] := graph[first][j];
  43.                   q2[(qhead + qcount) mod QSIZE] := second + peso[first][j];;
  44.                   inc(qcount);
  45.                 end;
  46.        end;
  47.  end;
  48.  
  49.  
  50. begin
  51.   (*assign(input,  'input.txt');  reset(input);
  52.   assign(output, 'output.txt'); rewrite(output);*)
  53.   readln(N,M); 
  54.   for h:=0 to M-1 do readln(S[h],E[h],P[h]);
  55.   for h:=0 to N-1 do
  56.    begin
  57.      setlength(graph[h], 1); (*graph è la lista di adiacenza del grafo orientato con i nodi adiacenti,*)                                    (*peso è la lista di adiacenza con i pesi relativi agli archi considerati*)
  58.      setlength(peso[h], 1);
  59.      (* all’inizio, la lista di adiacenza del nodo h ha dimensione 0
  60.        * e capacita’ 1.
  61.      *)
  62.      gsize[h] := 0;
  63.      gcapa[h] := 1;
  64.      dist[h] := 9223372036854775807; (*array delle distanze inizializzato con il massimo valore degli INT64*)
  65.   end;
  66.  for h:=0 to M-1 do
  67.       begin
  68.        a := S[h]; b := E[h]; c:=P[h];
  69.        (* se ho esaurito i posti nella lista di adiacenza del nodo a *)
  70.        if gsize[a] = gcapa[a] then
  71.             begin
  72.               (* allora raddoppio la sua capacita’ *)
  73.               gcapa[a] := gcapa[a] shl 1;
  74.               setlength(graph[a], gcapa[a]);
  75.               setlength(peso[a], gcapa[a]);
  76.             end;
  77.        graph[a][gsize[a]] := b;
  78.        peso[a][gsize[a]] := c;
  79.        inc(gsize[a]);
  80.     end;
  81.     inizio:=0;
  82.     for h:=1 to N do
  83.       begin
  84.          fine:=h;
  85.          bfs(inizio,fine,dist);
  86.       end;  
  87.             (* calcola le distanze partendo da inizio *)
  88.      for h:=0 to N-1 do
  89.          if dist[h]<>9223372036854775807 then write(dist[h],' ') 
  90.                                          else write('-1',' ');
  91. end.
  92.  
Success #stdin #stdout 0.02s 16624KB
comments (?)
stdin
copy 
2 1
1 0 1
stdout
copy 
0 -1
https://ideone.com/gldLIt
language:
Pascal (fpc 3.0.4)
created:
2 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!