graph/dijkstra.hpp

• View this file on GitHub
• Last update: 2023-03-24 23:12:28-07:00
• Include: #include "graph/dijkstra.hpp"

Depends on

• graph/graph-template.hpp

Verified with

• verify/aoj/dijkstra.test.cpp

Code

#include "../graph/graph-template.hpp"

#include <queue>
#include <utility>
#include <functional>

template<class T>
std::vector<T> dijkstra(WeightedGraph<T> &graph,int start=0){
    int n=(int)graph.size();
    std::vector<T> dist(n,(T)-1);
    std::vector<bool> ok(n,false);

    std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<std::pair<T,int>>> Q;
    dist[start]=0;
    Q.push({dist[start],start});

    while(!Q.empty()){
        int pos=Q.top().second;Q.pop();
        if(ok[pos])continue;
        ok[pos]=true;
        for(int i=0;i<(int)graph[pos].size();i++){
            if(dist[graph[pos][i].to]==-1 || dist[graph[pos][i].to]>dist[pos]+graph[pos][i].cost){
                dist[graph[pos][i].to]=dist[pos]+graph[pos][i].cost;
                Q.push({dist[graph[pos][i].to],graph[pos][i].to});
            }
        }
    }

    return dist;
}

#line 1 "graph/graph-template.hpp"
#include <iostream>
#include <vector>
template<class T>
struct edge{
    int from,to;
    T cost;
    
    edge(int to,T cost):from(-1),to(to),cost(cost){}
    edge(int from,int to,T cost):from(from),to(to),cost(cost){}

    edge &operator=(const int &x){
        to=x;
        return *this;
    }
};

template<class T>
using Edges = std::vector<edge<T>>;

template<class T>
using WeightedGraph = std::vector<Edges<T>>;
using UnweightedGraph = std::vector<std::vector<int>>;

UnweightedGraph input_graph(int N,int M,bool directed=false,bool one_origin=true){
    UnweightedGraph ret(N);
    for(int i=0;i<M;i++){
        int from,to;std::cin>>from>>to;
        if(one_origin)from--,to--;
        ret[from].push_back(to);
        if(!directed)ret[to].push_back(from);
    }
    return ret;
};

template<class T>
WeightedGraph<T> input_wgraph(int N,int M,bool directed=false,bool one_origin=true){
    WeightedGraph<T> ret(N);
    for(int i=0;i<M;i++){
        int from,to;T cost;std::cin>>from>>to>>cost;
        if(one_origin)from--,to--;
        ret[from].emplace_back(from,to,cost);
        if(!directed)ret[to].emplace_back(to,from,cost);
    }
    return ret;
};
#line 2 "graph/dijkstra.hpp"

#include <queue>
#include <utility>
#include <functional>

template<class T>
std::vector<T> dijkstra(WeightedGraph<T> &graph,int start=0){
    int n=(int)graph.size();
    std::vector<T> dist(n,(T)-1);
    std::vector<bool> ok(n,false);

    std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<std::pair<T,int>>> Q;
    dist[start]=0;
    Q.push({dist[start],start});

    while(!Q.empty()){
        int pos=Q.top().second;Q.pop();
        if(ok[pos])continue;
        ok[pos]=true;
        for(int i=0;i<(int)graph[pos].size();i++){
            if(dist[graph[pos][i].to]==-1 || dist[graph[pos][i].to]>dist[pos]+graph[pos][i].cost){
                dist[graph[pos][i].to]=dist[pos]+graph[pos][i].cost;
                Q.push({dist[graph[pos][i].to],graph[pos][i].to});
            }
        }
    }

    return dist;
}

Back to top page