src/graph/dijkstra.hpp

View this file on GitHub
Last update: 2022-12-30 13:43:35+09:00
Include: #include "src/graph/dijkstra.hpp"

Depends on

src/graph/template.hpp

Verified with

test/aoj/grl_1_a.test.cpp

Code

#pragma once

#include <bits/stdc++.h>
#include <limits>
using namespace std;

#include "./template.hpp"

template <typename T> struct Dijkstra {
private:
  int n;
  int start;
  Graph<T> graph;
  vector<T> dist;
  using P = pair<T, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  T MAX = numeric_limits<T>::max();

public:
  Dijkstra(int n, int start) : n(n), start(start), graph(n) {
    dist.resize(n, MAX);
    dist[start] = 0;
    que.push(P(0, start));
  }

  void add_edge(int start, int to, T cost) {
    graph[start].emplace_back(start, to, cost);
  }

  void build() {
    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int current = p.second;
      if (dist[current] < p.first) {
        continue;
      }
      for (auto &e : graph[current]) {
        if (dist[e.to] > dist[current] + e.cost) {
          dist[e.to] = dist[current] + e.cost;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
  }

  T shortest_path_value(int t) { return dist[t]; }

  bool is_unreachable(int t) { return dist[t] == MAX; }
};

#line 2 "src/graph/dijkstra.hpp"

#include <bits/stdc++.h>
#line 5 "src/graph/dijkstra.hpp"
using namespace std;

#line 2 "src/graph/template.hpp"

#line 4 "src/graph/template.hpp"
using namespace std;

template <typename T = long long> struct Edge {
  int from, to;
  T cost;
  Edge(int from, int to, T cost = 1) : from(from), to(to), cost(cost) {}
};

template <typename T = long long> using Edges = vector<Edge<T>>;
template <typename T = long long> using Graph = vector<Edges<T>>;

template <typename T = long long> using Matrix = vector<vector<T>>;
#line 8 "src/graph/dijkstra.hpp"

template <typename T> struct Dijkstra {
private:
  int n;
  int start;
  Graph<T> graph;
  vector<T> dist;
  using P = pair<T, int>;
  priority_queue<P, vector<P>, greater<P>> que;
  T MAX = numeric_limits<T>::max();

public:
  Dijkstra(int n, int start) : n(n), start(start), graph(n) {
    dist.resize(n, MAX);
    dist[start] = 0;
    que.push(P(0, start));
  }

  void add_edge(int start, int to, T cost) {
    graph[start].emplace_back(start, to, cost);
  }

  void build() {
    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int current = p.second;
      if (dist[current] < p.first) {
        continue;
      }
      for (auto &e : graph[current]) {
        if (dist[e.to] > dist[current] + e.cost) {
          dist[e.to] = dist[current] + e.cost;
          que.push(P(dist[e.to], e.to));
        }
      }
    }
  }

  T shortest_path_value(int t) { return dist[t]; }

  bool is_unreachable(int t) { return dist[t] == MAX; }
};