dijkstra.cpp

struct edge{
    int to;
    int cost;

    bool operator>(const edge &e)const{
        return cost > e.cost;
    }

    bool operator<(const edge &e)const{
        return cost < e.cost;
    }
};

void dijkstra(vector<vector<edge> > &g, vector<int> &dist, vector<int> &prev, int s){
    priority_queue<edge, vector<edge>, greater<edge> > pq;
    int V = g.size();

    fill(dist.begin(),dist.end(),INF);
    dist[s] = 0;

    pq.push((edge){s,0});

    while(!pq.empty()){
        auto v = pq.top(); pq.pop();
        if(dist[v.to] < v.cost) continue;

        for(auto next_v:g[v.to]){
            if(next_v.to != v.to and next_v.cost + dist[v.to] < dist[next_v.to]){
                dist[next_v.to] = next_v.cost + dist[v.to];
                pq.push((edge){next_v.to,dist[next_v.to]});
            }
        }
    }
}