Shortest Path in DAG🚩🚩

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;
	}
}