Untitled
plain_text
a month ago
1.9 kB
1
Indexable
Never
#include<iostream> #include<map> #include<list> #include<stack> #include<vector> using namespace std; //SHORTEST PATH IN DIRECTED ACYCLIC GRAPH class graph { public: map<int,list<pair<int,int>>> adj; void addedge(int u,int v,int weight){ pair<int,int> p=make_pair(v,weight); adj[u].push_back(p); } void printadj(){ for(auto i: adj){ cout<<i.first<<"->"; for(auto j:i.second){ cout<<"("<<j.first<<"-"<<j.second<<"),"; } cout<<endl; } } void dfstopo(int node,map<int,bool> &vis,stack<int> &topo){ vis[node]=true; for(auto nbr:adj[node]){ if(!vis[nbr.first]){ vis[nbr.first]=true; dfstopo(nbr.first,vis,topo); } } topo.push(node); } void shortdist(int src,vector<int> &dist,stack<int> &topo){ dist[src]=0; topo.push(src); while(!topo.empty()){ int top=topo.top(); topo.pop(); if(dist[top]==INT32_MAX) continue; for(auto i:adj[top]){ if(dist[top]+i.second<dist[i.first]) dist[i.first]=dist[top]+i.second; } } } }; int main(){ graph g; //make graph g.addedge(0,1,5); g.addedge(0,2,3); g.addedge(1,2,2); g.addedge(1,3,6); g.addedge(2,3,7); g.addedge(2,4,4); g.addedge(2,5,2); g.addedge(3,4,-1); g.addedge(4,5,-2); g.printadj(); int n=6; map<int,bool> vis; stack<int> topo; vector<int> dist(n,INT32_MAX); for(int i=0;i<n;i++){ if(!vis[i]){ g.dfstopo(i,vis,topo); } } int src=1; g.shortdist(src,dist,topo); for(int i=0;i<n;i++){ cout<<dist[i]<<"-"; } }