cpp/graph/graph_matrix.hpp

• View this file on GitHub
• Last update: 2024-10-29 23:42:15+09:00
• Include: #include "cpp/graph/graph_matrix.hpp"

Depends on

• 共通ヘッダー (cpp/template/small_template.hpp)

Required by

• cpp/graph/warshall_floyd.hpp

Verified with

• cpp/verify/warshall_floyd.test.cpp

Code

#pragma once
#include "template/small_template.hpp"

// グラフ(隣接行列)
template <class Cost = ll> class MatrixGraph {
  int n, m;
  vector<vector<Cost>> mat;
  vector<vector<Cost>> shortest_path_dist;
  vector<vector<int>> shortest_path_parent;
  bool negative_cycle = false;

public:
  static const Cost UNREACHABLE;

  MatrixGraph(int n_)
      : n(n_), m(0), mat(n_, vector<Cost>(n_, MatrixGraph::UNREACHABLE)) {
    for (int i = 0; i < n; ++i) {
      mat[i][i] = 0;
    }
  }

  void add_edge(int from, int to, Cost cost = 1) {
    mat[from][to] = cost;
    m++;
  }

  // 最短距離
  void warshall_floyd();
  Cost distance(int from, int to) { return shortest_path_dist[from][to]; }
  vector<int> get_shortest_path(int from, int to) {
    vector<int> path;
    for (int cur = to; cur != from; cur = shortest_path_parent[from][cur]) {
      path.emplace_back(cur);
      if (cur == -1) {
        return vector<int>();
      }
    }
    path.emplace_back(from);
    reverse(path.begin(), path.end());
    return path;
  }
  bool has_negative_cycle() const { return negative_cycle; }

  template <class T>
  friend std::ostream &operator<<(std::ostream &, const MatrixGraph<T> &);
};

template <class Cost>
const Cost MatrixGraph<Cost>::UNREACHABLE = numeric_limits<Cost>::max() >> 2;

template <class T>
ostream &operator<<(ostream &os, const MatrixGraph<T> &graph) {
  os << "N = " << graph.n << ", M = " << graph.m << '\n';
  for (int i = 0; i < graph.n; ++i) {
    for (int j = 0; j < graph.n; ++j) {
      os << graph.mat[i][j] << " \n"[j == graph.n - 1];
    }
  }
  return os;
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.0/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: template/small_template.hpp: line -1: no such header

Back to top page