CSES - Shortest Routes II

/**************************
*                         *
*    Author: Sukesh       *
*                         *
***************************/
#include<bits/stdc++.h>
#define FIO                 ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define int                 long long int
#define INF                 (int)1e14
using namespace std;

class ShortestPath{
    private:
        vector<pair<int,int>> paths; //assign to infinity
        int dest = 0;
        vector<bool> processed;

        void findShortestDijkstra(int src){
            paths[src].second = 0;
            priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
            pq.push({0,src}); // First element of the pair represents the parent node of the current node,
                              // second one represents the weight/distance of the current node from the source node

            while(!pq.empty()){
                auto dist = pq.top().first, node = pq.top().second;
                pq.pop();

                if(node==dest)
                    return;

                if(processed[node])
                    continue;
                processed[node] = 1;

                for(auto x: weighted[node]){
                    int node1 = x.first, wt = x.second;

                    if(dist+wt<paths[node1].second){
                        paths[node1].second = dist+wt;
                        paths[node1].first = node;
                        pq.push({paths[node1].second, node1});
                    }
                }
            }
        }

    public:
        vector<vector<pair<int,int>>> weighted;
        int dijkstra(int src, int end){
            int n = weighted.size()-1;

            paths.clear(), paths.resize(n+1, pair<int,int> ({0,INF}));
            processed.clear(), processed.resize(n+1);

            dest = end;
            findShortestDijkstra(src);
            if(paths[end].second>=INF){
                return -1;
            }

            return paths[end].second;
        }
};

vector<vector<pair<int,int>>> buildAdjList(int n, int e){
    vector<vector<pair<int,int>>> adj(n+1);
    for(int i = 0; i<e;i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    return adj;
}

void solve(){
    FIO;
    int n, e, q; cin >> n >> e >> q;
    ShortestPath s;
    s.weighted = buildAdjList(n,e);
    while(q--){
        int src, dest; cin >> src >> dest;
        cout << s.dijkstra(src,dest);
        cout << "\n";
    }
    return;
}

signed main(){
    FIO;

    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif

    int t=1;
    // cin>>t;
    while(t--)
        solve();

    #ifndef ONLINE_JUDGE
        cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    #endif
    return 0;
}