Untitled

mail@pastecode.io avatarunknown
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]<<"-";
    }
}