/*

A minimum distance of src from every other node present in graph with all non-negative weights (optimized algo) OR Negative weighted a-cyclic graph (Non-optimized Algo)

Complexity for dijktra's Algo -> O((V + E) log V)

E-Edges V-Vertices

We may add same node multiple times, hence total elements in a heap might be E. Hence, log(E).

Intreasting thing is to E = V*(V-1) => 2*log(V).

Slight modification: Think of adding a virtual node which joins an edge to each node. [Similar to multi source BFS]

Dikjtras can be applied 3-4 times... you reverse graph... node a to src and dest dist

https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/description/

*/

#include<bits/stdc++.h>

#define LIM 3000

#define INF 1e5+3

typedef pair<int,int> pii;

using namespace std;

//NOTE: Global variables are initailized to 0

vector<pii> adj[LIM];

vector<int> min_dist(LIM,INF);

//Each node in adj list represnts vertex and weight

void addEdge(int u, int v, int wt)

{

adj[u].push_back({v,wt});

adj[v].push_back({u,wt});

}

void dijktra(int src)

{

//MIN HEAP

// Keep distace or weight in first plce and indx in second

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

for(int i=0;i<LIM;i++)

min_dist[i]=INF; //Init to infinity

min_dist[src]=0;

pq.push({0,src});

while(pq.size())

{

int curr = pq.top().second;

pq.pop();

// Optimized to not traverse children if minDist which was encountered earlier was better

// This helps avoid traversing children if we already have a miniDist smaller traversed earlier

if( curr > min_dist[curr])

continue;

for(auto u : adj[curr])

{

int next = u.first;

int d = u.second;

//If previous distance is more than the new distance

if(min_dist[next] > min_dist[curr]+d)

{

pq.push({ d + min_dist[curr], next });

min_dist[next] = d+ min_dist[curr];

}

}

}

}

int main()

{

int V,i,E,src,u,v,wt;

cout<<"Enter number of vertices and edges: ";

cin>>V>>E;

cout<<endl;

for(i=0;i<E;i++)

{

cout<<"Enter vertex name u , v and weight: ";

cin>>u>>v>>wt;

addEdge(u,v,wt);

}

cout<<"Enter the source node: ";

cin>>src;

dijktra(src);

cout<<endl;

cout<<"Min distace all nodes from "<<src<<"is:\n";

for(int i=0;i<V;i++)

cout<<i<<"-"<<min_dist[i]<<endl;

}