djisktraCPP.cpp

#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int main(){
       int n,m,source;
       cin>>n>>m;
       vector<pair<int,int>> g[n+1]; // 1-indexed adjacency list for of graph
        
        int a,b,wt;
        for(int i=0;i<m;i++){
            cin>>a>>b>>wt;
            g[a].push_back(make_pair(b,wt));
            g[b].push_back(make_pair(a,wt));
        }

        cin>>source;
        // Dijkstra's algorithm begins from here

        priority_queue<pair<int,int>, vector<pair<int,int>> ,greater<pair<int,int>> pq; // min-heap ; In pair => (dist,from)
        vector<int> distTo(n+!, INT_MAX);  // 1-indexed array for calculating shortest paths; 
         
         distTo[source]=0; 
         pq.push(make_pair(0,source));

         while(!pq.empty()){
             int dist=pq.top().first;
             int prev=pq.top().second;
             pq.pop();

             vector<pair<int,int>>:: iterator it;
              for(it=g[prev].begin(); it!=g[prev].end();i++){
                  int next=it->first;
                  int nextDist=it->second;
                  if(distTo[next]> distTo[prev]+nextDist){
                      distTo[next]=distTo[prev]+nextDist;
                      pq.push(make_pair(distTo[next, next]));
                  }
              }
         }

         cout<<"The distances from source, "<<source<<", are:\n";
         for(int i=1;i<=n;i++){
             cout<<distTo[i]<<" ";
             cout<<"\n";

             return 0;
         }
}