Heap Dijkstra

//============================================================================
// Name          : HIGHWAYS.cpp
// Author        : LDT
// Version        : 2.0
// Copyright      : Copyright © by Tiger
// Description    : Using the DIJKSTRA with HEAP
// Problem source : http://www.spoj.pl/problems/HIGHWAYS/
//  - use the priority_queue for easy implement, but it less effect than the real Heap Dijkstra
//  - priority_queue.top only return the bigest, not the smallest, base on the compare < (less)
//  - greater <ii> first compare x.first then x.second
//============================================================================

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

const int cmaxn = 100010;
const int cinf  = 1000000000;

int main() {     
    int sotest;
    scanf("%d",&sotest);
    for (int dem = 1; dem <= sotest; dem++) {
        int N,M,S,F;

        scanf("%d %d %d %d",&N,&M,&S,&F);
        vvii G(N);
         
        for (int i = 1; i<=M; i++){
            int u,v,w;
            scanf("%d %d %d",&u,&v,&w);
            ii k1,k2;
            k1.first = w;
            k1.second = u-1;
            G[v-1].push_back(k1);
           
            k2.first = w;
            k2.second = v-1;
            G[u-1].push_back(k2);
        }

        S--;
        F--;
        //initialize
        vi D(N, cinf);// distance from start vertex to each vertex
   
        priority_queue<ii,vii,greater<ii> > Q;
        //type - container - compare
       
        D[S] = 0;
        Q.push(ii(0,S));
       
        // iterate while queue is not empty
        while(!Q.empty()) {
            // fetch the nearest element
            ii top = Q.top();
            Q.pop();
   
            // v is vertex index, d is the distance
            int v = top.second, d = top.first;
            if (v == F)
                break;
            if (d <= D[v]) {
                // iterate through all outcoming edges from v

                for (vii::iterator it = G[v].begin(); it != G[v].end(); it++){
                    int v2 = it->second, cost = it->first;
                    if(D[v2] > D[v] + cost) {
                        // update distance if possible
                        D[v2] = D[v] + cost;
                        // add the vertex to queue
                        Q.push(ii(D[v2],v2));
                    }
                }
            }
        }
   
        if (D[F] == cinf)     
            printf("NONE\n");
        else
            printf("%d\n",D[F]);
    }
    return EXIT_SUCCESS;
}

//============================================================================
// Name          : SHPATH.cpp
// Author        : LDT
// Version        : 2.0
// Copyright      : Copyright © by Tiger
// Description    : Using the DIJKSTRA with HEAP
// Problem source : http://www.spoj.pl/problems/SHPATH/
//============================================================================

#include <cstdlib>
#include <iostream>

using namespace std;

const int cMaxV = 10000;
const int cMaxE = 500000;
const int cInf = 200000;

int gN;
string gName[cMaxV];
int gAdj[cMaxE];
int gAdjCost[cMaxE];
int gHead[cMaxV];//canh ke dinh i chay tu dinh[i-1]+1 --> dinh[i]
int gD[cMaxV];
//for DIJKSTRA
bool gFree[cMaxV]; //da visit chua?
int gHeap[cMaxV]; //heap
int gPos[cMaxV]; //vi tri cua nut do trong heap
int gNHeap; //so luong dinh co trong heap

void readf() {
    gN = 0;
    gHead[0] = 0;

    //cin >> gN;
    scanf("%d",&gN);

    int p;
    int u, v;
    int idA = gHead[0];
    for (int i = 1; i <= gN; i++) {
        cin >> gName[i];
        //scanf("%s",gName[i]);
        //cin >> p;
        scanf("%d",&p);
        gHead[i] = gHead[i - 1] + p;
        for (int j = 1; j <= p; j++) {
            //cin >> u >> v;
            scanf("%d%d",&u,&v);
            idA++;
            gAdj[idA] = u;
            gAdjCost[idA] = v;
        }
    }
}

void update(int v) {
    //dinh v vua duoc sua nhan, can phai chinh lai HEAP
    int pParent, pChild;
    pChild = gPos[v]; //pChild la vi tri cua V trong Heap
    if (pChild == 0) {
        //Neu v chua co trong heap thi
        //1. heap bo sung them mot phan tu
        //2. coi child = nut la cuoi trong heap
        gNHeap++;
        pChild = gNHeap;
    }

    //dua nut v len dung vi tri cua no trong cay
    pParent = pChild / 2; //pParent la nut cha cua pChild;
    while ((pParent > 0) && (gD[gHeap[pParent]] > gD[v])) {
        //neu dinh luu o nut pParent uu tien kem hon V thi no se bi day xuong nut con pChild
        gHeap[pChild] = gHeap[pParent]; //day dinh luu nut cha xuong nut con
        gPos[gHeap[pChild]] = pChild; //ghi nhan la vi tri moi cua dinh do
        pChild = pParent; //tiep tuc xet len nut phia goc
        pParent = pParent / 2;
    }
    //thao tac "keo xuong" tao nen 1 "khoang trong" tai nut child cua Heap, dinh V duoc dat vao day
    gHeap[pChild] = v;
    gPos[v] = pChild;
}

int pop() {
    int pRe = gHeap[1]; //nut goc Heap chua dinh co nhan tu do thap nhat
    int pV = gHeap[gNHeap]; //v la dinh la cuoi cua Heap, se duoc dao len dau va vun dong
    gNHeap--;
    int pR = 1; //bat dau tu nut goc, vi tri se dua nut cuoi len de hoan thien cay
    int pC;
    while (pR * 2 <= gNHeap) {
        //chung nao r chua phai la la'
        pC = pR * 2; //chon c la nut chua dinh uu tien hon trong 2 nut con
        if ((pC < gNHeap) && (gD[gHeap[pC + 1]] < gD[gHeap[pC]]))
            pC++;

        //neu uu tien hon ca dinh chua trong C thi thoat ngay
        if (gD[pV] <= gD[gHeap[pC]])
            break;
        gHeap[pR] = gHeap[pC]; // chuyen dinh luu o nut con pC len nut cha pR
        gPos[gHeap[pR]] = pR; //ghi nhan lai vi tri moi trong gHeap cua dinh do

        //duyet tiep xuong duoi cay
        pR = pC; //gan nut cha = nut con va lap lai
    }
    gHeap[pR] = pV; //dinh v se duoc dat vao nut pR de bao toan cau truc Heap
    gPos[pV] = pR;

    return pRe;
}

void ijk(int S, int F) {
    //Dijkstra
    //initialize
    for (int i = 1; i <= gN; i++)
        gD[i] = cInf;
    gD[S] = 0;
    for (int i = 1; i <= gN; i++) {
        gFree[i] = true;
    }

    memset(gPos, 0, sizeof(gPos));

    gNHeap = 0;

    //create the Heaptree
    update(S);
    int pU;
    int pV;

    //Loop
    do {
        pU = pop(); //chon pU la dinh tu do co nhan no nhat
        //cout << " u = " << pU << endl;
        if (pU == F) //neu dinh pU la dinh F thi dung ngay
            break;
        gFree[pU] = false; //co dinh nhan do
        for (int pIv = gHead[pU-1] + 1; pIv <= gHead[pU]; pIv++) {
            //duyet danh sach ke
            pV = gAdj[pIv];
            if ((gFree[pV]) && (gD[pV] > gD[pU] + gAdjCost[pIv])) {
                //toi uu hoa nhan cua cac dinh tu do  ke voi u
                gD[pV] = gD[pU] + gAdjCost[pIv];
                update(pV);
            }
        }
    } while (gNHeap > 0);
    //printHeap();

}

int findID(string na) {
    for (int i = 1; i <= gN; i++) {
        if (gName[i] == na) {
            return i;
        }
    }
    return 0;
}

void solve() {
    int r;
    string n1, n2;
    int id1, id2;
    //cin >> r;
    scanf("%d",&r);
    for (int i = 1; i <= r; i++) {
        cin >> n1 >> n2;
        //scanf("%s %s",&n1,&n2);
        id1 = findID(n1);
        id2 = findID(n2);
        ijk(id1, id2);
        //cout <<" id1 = " <<id1 <<" id2 = " <<id2 <<endl;
        //printIJK();
        cout << gD[id2] << endl;
    }

}

int main(int argc, char *argv[]) {

    int sotest;
    //cin >> sotest;
    scanf("%d",&sotest);
    for (int i = 1; i <= sotest; i++) {
        readf();
        //printA();
        solve();
    }

    http://cin.close();
    //system("PAUSE");
    return EXIT_SUCCESS;
}