Program TheShortestPath; Type des = Record cost,dest: Longword; End; Var i,t,r: Byte; j,k,n: Word; adj,heap: Array of des; last,HeapIdx,dist: Array[0..10000] of Longint; city: Array[1..10000] of String[10]; visited: Array[1..10000] of Boolean; heap_length: Longint; source,destination: String[10]; Function Div2(indx: Longword): Longword; Begin Div2:= (indx + 1) div 2 - 1; End; Procedure Swap(indx1,indx2: Longword); Var temp: des; Begin heapidx[heap[indx1].dest]:= indx2; heapidx[heap[indx2].dest]:= indx1; temp:= heap[indx1]; heap[indx1]:= heap[indx2]; heap[indx2]:= temp; End; Procedure MinHeapify(indx: Longword); Var left,right,min: Longword; Begin left:= 2 * (indx + 1) - 1; right:= 2 * (indx + 1); min:= indx; If (left <= heap_length) and (heap[left].cost < heap[min].cost) then min:= left; If (right <= heap_length) and (heap[right].cost < heap[min].cost) then min:= right; If min <> indx then Begin Swap(indx,min); MinHeapify(min); End; End; Procedure Pop; Begin dist[heap[0].dest]:= -1; heap[0]:= heap[heap_length]; heap_length:= heap_length - 1; If heap_length <> -1 then MinHeapify(0); End; Procedure UpHeap(indx: Longword); Begin While (indx <> 0) and (heap[Div2(indx)].cost > heap[indx].cost) do Begin Swap(indx,Div2(indx)); indx:= Div2(indx); End; End; Procedure Push(cityindex,cost: Longword); Begin visited[cityindex]:= true; heap_length:= heap_length + 1; heap[heap_length].dest:= cityindex; heap[heap_length].cost:= cost; heapidx[cityindex]:= heap_length; dist[cityindex]:= cost; Upheap(heap_length); End; Procedure Update(indx,value: Longword); Begin heap[indx].cost:= value; dist[heap[indx].dest]:= value; Upheap(indx); End; Procedure Findpath(cityindx: Longword;destination: String); Var i: Longword; peek: des; Begin heap[0].dest:= cityindx; heap[0].cost:= 0; heap_length:= 0; Fillchar(visited,sizeof(visited),false); visited[heap[0].dest]:= true; Repeat peek:= heap[0]; Pop; If city[peek.dest] = destination then Begin Writeln(peek.cost); exit; End; For i:= last[peek.dest-1]+1 to last[peek.dest] do If not visited[adj[i].dest] then Push(adj[i].dest,adj[i].cost + peek.cost) Else If dist[adj[i].dest] > peek.cost + adj[i].cost then Update(heapidx[adj[i].dest], peek.cost + adj[i].cost); Until 1 = 0; End; Procedure ReadString(Var s1,s2: String); Var i: Byte; Begin Readln(s1); i:= 1; While s1[i] <> ' ' do i:= i + 1; s2:= Copy(s1,i+1,Length(s1)-i); s1:= Copy(s1,1,i-1); End; Begin Readln(t); last[0]:= -1; For i:= 1 to t do Begin Readln(n); SetLength(adj,n*n); For j:= 1 to n do Begin Readln(city[j]); Readln(last[j]); last[j]:= last[j-1] + last[j]; For k:= last[j-1]+1 to last[j] do Readln(adj[k].dest,adj[k].cost); End; SetLength(adj,last[n]+1); SetLength(heap,last[n]+1); Readln(r); For j:= 1 to r do Begin ReadString(source,destination); If source <> destination then For k:= 1 to n do If city[k] = source then Begin Findpath(k,destination); break; End else Else Writeln('0'); End; Readln; End; End.