Spoj SHPATH Solution

#include<bits/stdc++.h>

#define pii pair<int, int>

#define INF 1<<30

#define N 10100

using namespace std;

int node;

int dijstkra(vector<pii>adj[], int start, int finish)

{

    priority_queue<pii, vector<pii>, greater<pii>> q;

    vector<int>d(N, INF);

    d[start] = 0;

    q.push(pii(0, start));

    while(!q.empty())

    {

        int u = q.top().second;

        q.pop();

        

        if(u == finish)

return d[u];

        for(auto x : adj[u])

        {

            int v = x.first;

            int w = x.second;

            if(d[v] > d[u] + w)

            {

                d[v] = d[u] + w;

                q.push(pii(d[v], v));

            }

        }

    }

    

    return d[finish];

}

int main()

{

ios_base :: sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

    int t;

    cin >> t;

    while(t--)

    {

        cin >> node;

        vector<pii>adj[node+10];

        map<string, int>mp;

        for(int i=1; i<=node; i++)

        {

            string st;

            cin >> st;

            mp[st] = i;

            int n1, w, m;

            cin >> m;

            for(int j=1; j<=m; j++)

            {

                cin >> n1 >> w;

                adj[i].push_back(pii(n1, w));

            }

        }

        int k;

        cin >> k;

        string st1, st2;

        for(int j=1; j<=k; j++)

        {

            cin >> st1 >> st2;

            int node1 = mp[st1];

            int node2 = mp[st2];

            int result = dijstkra(adj, node1, node2);

            cout << result << "\n";

        }

    }

    return 0;

}