SHPATH-The Shortest Path

The Shortest Path

Given Below code is for shpath spoj or the shortest path spoj.

/*
===================================================
Name :- Nishant Raj
Email :- raj.nishant360@gmail.com
College :- Indian School of Mines
Branch :- Computer Science and Engineering
Time :- 08 September 2015 (Tuesday) 20:11
===================================================*/
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define ll long long
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define mod 1000000009
struct cmp
{
    bool operator()(const pair<int , int> &a , const pair<int , int> &b){
        return a.first > b.first;
    }
};
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        string s;
        vector<int> graph[n+9];
        vector<vector<int> > cost(n+1 , vector<int>(n+1 , 0));
        map<string, int> map_name;
        for(int i = 1 ; i <= n ; i++){
            cin>>s;
            map_name[s] = i;
            int path , k , c;
            cin>>path;
            for(int j = 0 ; j < path ; j++){
                cin>>k>>c;
                graph[i].pb(k);
                cost[i][k] = c;
            }
        }
        int k;
        cin>>k;
        while(k--){
            char source_temp[12] , dest_temp[12];
            string source , dest;
            source.assign(source_temp);
            dest.assign(dest_temp);
            cin>>source>>dest;
            priority_queue<pii , vector<pii >, cmp > pq;
            ll dist[n+9];
            fill(dist , dist+n , INT_MAX-100000);
            int dist_num = map_name[dest] , source_num = map_name[source];
            dist[source_num] = 0;
            pq.push(mp(0 , source_num));
            while(!pq.empty()){
                int wt = pq.top().first;
                int node = pq.top().second;
                pq.pop();
                if(node == dist_num){
                    cout<<wt<<endl;
                    break;
                }
                for(auto it:graph[node]){
                    if(dist[it] > dist[node] + cost[node][it]){
                        dist[it] = dist[node] + cost[node][it];
                        pq.push(mp(dist[it] , it));
                    }
                }
            }
        }
    }
    
    return 0;
}