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