dijkstra.cpp

  std::vector<int> dijkstra(const Graph& g,int s){
    std::vector<int> dist(g.num_v,INT_MAX);
    std::vector<bool> b_set(g.num_v,false);

    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >  dist_pq;
    dist[s] = 0;
    dist_pq.push(make_pair(dist[s],s));

    while(!dist_pq.empty()){
      int cur_node = dist_pq.top().second;
      dist_pq.pop();
      if(!b_set[cur_node]){
        b_set[cur_node] = true;
        for(auto e: g.nodes[cur_node].out_edges){
          if( !b_set[e.edge.second]&& dist[e.edge.second] > dist[cur_node] + e.weight){
            dist[e.edge.second] = dist[cur_node] + e.weight;
            dist_pq.push(make_pair(dist[e.edge.second],e.edge.second));
          }
        }
      }

    }
    return dist;  
  }