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.
UHJvZ3JhbSBUaGVTaG9ydGVzdFBhdGg7ClR5cGUKICBkZXMgPSBSZWNvcmQKICAgICAgICAgIGNvc3QsZGVzdDogTG9uZ3dvcmQ7CiAgICAgICAgRW5kOwpWYXIKICBpLHQscjogQnl0ZTsKICBqLGssbjogV29yZDsKICBhZGosaGVhcDogQXJyYXkgb2YgZGVzOwogIGxhc3QsSGVhcElkeCxkaXN0OiBBcnJheVswLi4xMDAwMF0gb2YgTG9uZ2ludDsKICBjaXR5OiBBcnJheVsxLi4xMDAwMF0gb2YgU3RyaW5nWzEwXTsKICB2aXNpdGVkOiBBcnJheVsxLi4xMDAwMF0gb2YgQm9vbGVhbjsKICBoZWFwX2xlbmd0aDogTG9uZ2ludDsKICBzb3VyY2UsZGVzdGluYXRpb246IFN0cmluZ1sxMF07CgpGdW5jdGlvbiBEaXYyKGluZHg6IExvbmd3b3JkKTogTG9uZ3dvcmQ7CkJlZ2luCiAgRGl2Mjo9IChpbmR4ICsgMSkgZGl2IDIgLSAxOwpFbmQ7ClByb2NlZHVyZSBTd2FwKGluZHgxLGluZHgyOiBMb25nd29yZCk7ClZhciB0ZW1wOiBkZXM7CkJlZ2luCiAgaGVhcGlkeFtoZWFwW2luZHgxXS5kZXN0XTo9IGluZHgyOwogIGhlYXBpZHhbaGVhcFtpbmR4Ml0uZGVzdF06PSBpbmR4MTsKICB0ZW1wOj0gaGVhcFtpbmR4MV07CiAgaGVhcFtpbmR4MV06PSBoZWFwW2luZHgyXTsKICBoZWFwW2luZHgyXTo9IHRlbXA7CkVuZDsKUHJvY2VkdXJlIE1pbkhlYXBpZnkoaW5keDogTG9uZ3dvcmQpOwpWYXIgbGVmdCxyaWdodCxtaW46IExvbmd3b3JkOwpCZWdpbgogIGxlZnQ6PSAyICogKGluZHggKyAxKSAtIDE7CiAgcmlnaHQ6PSAyICogKGluZHggKyAxKTsKICBtaW46PSBpbmR4OwoKICBJZiAobGVmdCA8PSBoZWFwX2xlbmd0aCkgYW5kIChoZWFwW2xlZnRdLmNvc3QgPCBoZWFwW21pbl0uY29zdCkgdGhlbgogICAgbWluOj0gbGVmdDsKICBJZiAocmlnaHQgPD0gaGVhcF9sZW5ndGgpIGFuZCAoaGVhcFtyaWdodF0uY29zdCA8IGhlYXBbbWluXS5jb3N0KSB0aGVuCiAgICBtaW46PSByaWdodDsKICBJZiBtaW4gPD4gaW5keCB0aGVuCiAgQmVnaW4KICAgIFN3YXAoaW5keCxtaW4pOwogICAgTWluSGVhcGlmeShtaW4pOwogIEVuZDsKRW5kOwpQcm9jZWR1cmUgUG9wOwpCZWdpbgogIGRpc3RbaGVhcFswXS5kZXN0XTo9IC0xOwogIGhlYXBbMF06PSBoZWFwW2hlYXBfbGVuZ3RoXTsKICBoZWFwX2xlbmd0aDo9IGhlYXBfbGVuZ3RoIC0gMTsKICBJZiBoZWFwX2xlbmd0aCA8PiAtMSB0aGVuIE1pbkhlYXBpZnkoMCk7CkVuZDsKUHJvY2VkdXJlIFVwSGVhcChpbmR4OiBMb25nd29yZCk7CkJlZ2luCiAgV2hpbGUgKGluZHggPD4gMCkgYW5kIChoZWFwW0RpdjIoaW5keCldLmNvc3QgPiBoZWFwW2luZHhdLmNvc3QpIGRvCiAgQmVnaW4KICAgIFN3YXAoaW5keCxEaXYyKGluZHgpKTsKICAgIGluZHg6PSBEaXYyKGluZHgpOwogIEVuZDsKRW5kOwpQcm9jZWR1cmUgUHVzaChjaXR5aW5kZXgsY29zdDogTG9uZ3dvcmQpOwpCZWdpbgogIHZpc2l0ZWRbY2l0eWluZGV4XTo9IHRydWU7CiAgaGVhcF9sZW5ndGg6PSBoZWFwX2xlbmd0aCArIDE7CiAgaGVhcFtoZWFwX2xlbmd0aF0uZGVzdDo9IGNpdHlpbmRleDsKICBoZWFwW2hlYXBfbGVuZ3RoXS5jb3N0Oj0gY29zdDsKICBoZWFwaWR4W2NpdHlpbmRleF06PSBoZWFwX2xlbmd0aDsKICBkaXN0W2NpdHlpbmRleF06PSBjb3N0OwogIFVwaGVhcChoZWFwX2xlbmd0aCk7CkVuZDsKUHJvY2VkdXJlIFVwZGF0ZShpbmR4LHZhbHVlOiBMb25nd29yZCk7CkJlZ2luCiAgaGVhcFtpbmR4XS5jb3N0Oj0gdmFsdWU7CiAgZGlzdFtoZWFwW2luZHhdLmRlc3RdOj0gdmFsdWU7CiAgVXBoZWFwKGluZHgpOwpFbmQ7ClByb2NlZHVyZSBGaW5kcGF0aChjaXR5aW5keDogTG9uZ3dvcmQ7ZGVzdGluYXRpb246IFN0cmluZyk7ClZhciBpOiBMb25nd29yZDsgcGVlazogZGVzOwpCZWdpbgogIGhlYXBbMF0uZGVzdDo9IGNpdHlpbmR4OwogIGhlYXBbMF0uY29zdDo9IDA7CiAgaGVhcF9sZW5ndGg6PSAwOwogIEZpbGxjaGFyKHZpc2l0ZWQsc2l6ZW9mKHZpc2l0ZWQpLGZhbHNlKTsKICB2aXNpdGVkW2hlYXBbMF0uZGVzdF06PSB0cnVlOwogIFJlcGVhdAogICAgcGVlazo9IGhlYXBbMF07CiAgICBQb3A7CiAgICBJZiBjaXR5W3BlZWsuZGVzdF0gPSBkZXN0aW5hdGlvbiB0aGVuCiAgICBCZWdpbgogICAgICBXcml0ZWxuKHBlZWsuY29zdCk7CiAgICAgIGV4aXQ7CiAgICBFbmQ7CgoKICAgIEZvciBpOj0gbGFzdFtwZWVrLmRlc3QtMV0rMSB0byBsYXN0W3BlZWsuZGVzdF0gZG8KICAgICAgSWYgbm90IHZpc2l0ZWRbYWRqW2ldLmRlc3RdIHRoZW4KICAgICAgICAgIFB1c2goYWRqW2ldLmRlc3QsYWRqW2ldLmNvc3QgKyBwZWVrLmNvc3QpCiAgICAgIEVsc2UKICAgICAgICBJZiBkaXN0W2FkaltpXS5kZXN0XSA+IHBlZWsuY29zdCArIGFkaltpXS5jb3N0IHRoZW4KICAgICAgICAgIFVwZGF0ZShoZWFwaWR4W2FkaltpXS5kZXN0XSwgcGVlay5jb3N0ICsgYWRqW2ldLmNvc3QpOwogIFVudGlsIDEgPSAwOwpFbmQ7ClByb2NlZHVyZSBSZWFkU3RyaW5nKFZhciBzMSxzMjogU3RyaW5nKTsKVmFyIGk6IEJ5dGU7CkJlZ2luCiAgUmVhZGxuKHMxKTsKICBpOj0gMTsKICBXaGlsZSBzMVtpXSA8PiAnICcgZG8gaTo9IGkgKyAxOwogIHMyOj0gQ29weShzMSxpKzEsTGVuZ3RoKHMxKS1pKTsKICBzMTo9IENvcHkoczEsMSxpLTEpOwpFbmQ7CkJlZ2luCiAgUmVhZGxuKHQpOwogIGxhc3RbMF06PSAtMTsKICBGb3IgaTo9IDEgdG8gdCBkbwogIEJlZ2luCiAgICBSZWFkbG4obik7CiAgICBTZXRMZW5ndGgoYWRqLG4qbik7CiAgICBGb3Igajo9IDEgdG8gbiBkbwogICAgQmVnaW4KICAgICAgUmVhZGxuKGNpdHlbal0pOwogICAgICBSZWFkbG4obGFzdFtqXSk7CiAgICAgIGxhc3Rbal06PSBsYXN0W2otMV0gKyBsYXN0W2pdOwogICAgICBGb3Igazo9IGxhc3Rbai0xXSsxIHRvIGxhc3Rbal0gZG8KICAgICAgICBSZWFkbG4oYWRqW2tdLmRlc3QsYWRqW2tdLmNvc3QpOwogICAgRW5kOwogICAgU2V0TGVuZ3RoKGFkaixsYXN0W25dKzEpOwogICAgU2V0TGVuZ3RoKGhlYXAsbGFzdFtuXSsxKTsKCiAgICBSZWFkbG4ocik7CiAgICBGb3Igajo9IDEgdG8gciBkbwogICAgQmVnaW4KICAgICAgUmVhZFN0cmluZyhzb3VyY2UsZGVzdGluYXRpb24pOwogICAgICBJZiBzb3VyY2UgPD4gZGVzdGluYXRpb24gdGhlbgogICAgICAgIEZvciBrOj0gMSB0byBuIGRvCiAgICAgICAgICBJZiBjaXR5W2tdID0gc291cmNlIHRoZW4KICAgICAgICAgIEJlZ2luCiAgICAgICAgICAgIEZpbmRwYXRoKGssZGVzdGluYXRpb24pOwogICAgICAgICAgICBicmVhazsKICAgICAgICAgIEVuZCBlbHNlCiAgICAgIEVsc2UgV3JpdGVsbignMCcpOwogICAgRW5kOwogICAgUmVhZGxuOwogIEVuZDsKRW5kLgo=