fork(1) download
copy 
  1. Program TheShortestPath;
  2. Type
  3.   des = Record
  4.           cost,dest: Longword;
  5.         End;
  6. Var
  7.   i,t,r: Byte;
  8.   j,k,n: Word;
  9.   adj,heap: Array of des;
  10.   last,HeapIdx,dist: Array[0..10000] of Longint;
  11.   city: Array[1..10000] of String[10];
  12.   visited: Array[1..10000] of Boolean;
  13.   heap_length: Longint;
  14.   source,destination: String[10];
  15.  
  16. Function Div2(indx: Longword): Longword;
  17. Begin
  18.   Div2:= (indx + 1) div 2 - 1;
  19. End;
  20. Procedure Swap(indx1,indx2: Longword);
  21. Var temp: des;
  22. Begin
  23.   heapidx[heap[indx1].dest]:= indx2;
  24.   heapidx[heap[indx2].dest]:= indx1;
  25.   temp:= heap[indx1];
  26.   heap[indx1]:= heap[indx2];
  27.   heap[indx2]:= temp;
  28. End;
  29. Procedure MinHeapify(indx: Longword);
  30. Var left,right,min: Longword;
  31. Begin
  32.   left:= 2 * (indx + 1) - 1;
  33.   right:= 2 * (indx + 1);
  34.   min:= indx;
  35.  
  36.   If (left <= heap_length) and (heap[left].cost < heap[min].cost) then
  37.     min:= left;
  38.   If (right <= heap_length) and (heap[right].cost < heap[min].cost) then
  39.     min:= right;
  40.   If min <> indx then
  41.   Begin
  42.     Swap(indx,min);
  43.     MinHeapify(min);
  44.   End;
  45. End;
  46. Procedure Pop;
  47. Begin
  48.   dist[heap[0].dest]:= -1;
  49.   heap[0]:= heap[heap_length];
  50.   heap_length:= heap_length - 1;
  51.   If heap_length <> -1 then MinHeapify(0);
  52. End;
  53. Procedure UpHeap(indx: Longword);
  54. Begin
  55.   While (indx <> 0) and (heap[Div2(indx)].cost > heap[indx].cost) do
  56.   Begin
  57.     Swap(indx,Div2(indx));
  58.     indx:= Div2(indx);
  59.   End;
  60. End;
  61. Procedure Push(cityindex,cost: Longword);
  62. Begin
  63.   visited[cityindex]:= true;
  64.   heap_length:= heap_length + 1;
  65.   heap[heap_length].dest:= cityindex;
  66.   heap[heap_length].cost:= cost;
  67.   heapidx[cityindex]:= heap_length;
  68.   dist[cityindex]:= cost;
  69.   Upheap(heap_length);
  70. End;
  71. Procedure Update(indx,value: Longword);
  72. Begin
  73.   heap[indx].cost:= value;
  74.   dist[heap[indx].dest]:= value;
  75.   Upheap(indx);
  76. End;
  77. Procedure Findpath(cityindx: Longword;destination: String);
  78. Var i: Longword; peek: des;
  79. Begin
  80.   heap[0].dest:= cityindx;
  81.   heap[0].cost:= 0;
  82.   heap_length:= 0;
  83.   Fillchar(visited,sizeof(visited),false);
  84.   visited[heap[0].dest]:= true;
  85.   Repeat
  86.     peek:= heap[0];
  87.     Pop;
  88.     If city[peek.dest] = destination then
  89.     Begin
  90.       Writeln(peek.cost);
  91.       exit;
  92.     End;
  93.  
  94.  
  95.     For i:= last[peek.dest-1]+1 to last[peek.dest] do
  96.       If not visited[adj[i].dest] then
  97.           Push(adj[i].dest,adj[i].cost + peek.cost)
  98.       Else
  99.         If dist[adj[i].dest] > peek.cost + adj[i].cost then
  100.           Update(heapidx[adj[i].dest], peek.cost + adj[i].cost);
  101.   Until 1 = 0;
  102. End;
  103. Procedure ReadString(Var s1,s2: String);
  104. Var i: Byte;
  105. Begin
  106.   Readln(s1);
  107.   i:= 1;
  108.   While s1[i] <> ' ' do i:= i + 1;
  109.   s2:= Copy(s1,i+1,Length(s1)-i);
  110.   s1:= Copy(s1,1,i-1);
  111. End;
  112. Begin
  113.   Readln(t);
  114.   last[0]:= -1;
  115.   For i:= 1 to t do
  116.   Begin
  117.     Readln(n);
  118.     SetLength(adj,n*n);
  119.     For j:= 1 to n do
  120.     Begin
  121.       Readln(city[j]);
  122.       Readln(last[j]);
  123.       last[j]:= last[j-1] + last[j];
  124.       For k:= last[j-1]+1 to last[j] do
  125.         Readln(adj[k].dest,adj[k].cost);
  126.     End;
  127.     SetLength(adj,last[n]+1);
  128.     SetLength(heap,last[n]+1);
  129.  
  130.     Readln(r);
  131.     For j:= 1 to r do
  132.     Begin
  133.       ReadString(source,destination);
  134.       If source <> destination then
  135.         For k:= 1 to n do
  136.           If city[k] = source then
  137.           Begin
  138.             Findpath(k,destination);
  139.             break;
  140.           End else
  141.       Else Writeln('0');
  142.     End;
  143.     Readln;
  144.   End;
  145. End.
  146.  
Success #stdin #stdout 0s 508KB
comments (?)
stdin
copy 
1
4
gdansk
2
2 1
3 3
bydgoszcz
3
1 1
3 1
4 4
torun
3
1 3
2 1
4 1
warszawa
2
2 4
3 1
2
gdansk warszawa
bydgoszcz warszawa
stdout
copy 
3
2
https://ideone.com/Dnh5Zw
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
secret

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!