vector<pair<ll, ll>> g[100001]; vector<ll> visi(100001, false); /* ->single source shortest path in DAG(directed acyclic graph) Steps:- 1)find the toposort of graph using dfs in a stack 2)initialize ,an array distance of size of vertices+1 with values to infinity 3)now,make the value of source to be zero in distance array 4)now,run a loop while the stack is not empty ->get the curr=top of stack, pop from stack ->if(dist[curr]!=inf) ->iterate through the adjancey list of curr -> change dist[child] = min(dist[child],weight-to-reach-child from curr +dist[curr]); 5) the distance array will contain the distance of each vertex from the source vertex Time complexity = 2*O(n+m) ->n=no of vertices,m = no of edges */ #define inf 1e9+7 //function to find topoSort void topoSort(ll s, stack<ll> &st) { if (visi[s]) return; visi[s] = true; for (pair<ll, ll> p : g[s]) { if (visi[p.first] == false) dfs(p.first, st); } st.push(s); } //find the distance void findDistace(ll s, ll n) { stack<ll> st;//this stack is passed to topoSort function topoSort(0, st); vector<ll> dist(100001, inf);//initializing the dist array and giving value to infinity dist[s] = 0;//marking the dist of source to 0 //loop while the stack is not empty while (!st.empty()) { ll curr = st.top(); if (dist[curr] != inf) { for (pair<ll, ll> p : g[curr]) { //iterating for the adjacency list of curr ll child = p.first, weight = p.second; dist[child] = min(dist[child], weight + dist[curr]); //assigining the min dist to chid } } st.pop(); } //this distace array will contain the distace of each vertex from source vertex for (ll i = 0; i < n; i++) { cout << i << "-->" << dist[i] << endl; } }