graph/dijkstra.hpp

• View this file on GitHub
• Last update: 1970-01-01 00:00:00+00:00
• Include: #include "graph/dijkstra.hpp"

Code

#pragma once

#include "./base.hpp"
#include "./graph-type.hpp"

#include <algorithm>
#include <limits>
#include <queue>
#include <vector>


namespace matumoto {
  template <typename Cost>
  struct Dijkstra {
    using Edge = WeightedEdge<Cost>;
    vector<Cost> ds;
    vector<int> bs;

    static constexpr Cost inf() {
      return numeric_limits<Cost>::max() / 2;
    }

    Dijkstra(vector<pair<Cost, int>> g, int start): ds(g.size(), inf()), bs(g.size(), -1) {
      assert(0 <= start and start < g.size());
      auto G = g.graph();
      priority_queue<Edge, vector<Edge>, greater<Edge>> Q;
      ds[start] = 0;
      Q.emplace(start, ds[start]);

      while (!Q.empty()) {
        Edge p = Q.top();
        int v = p.to();
        Q.pop();

        if (ds[v] < p.cost())
          continue;

        for (Edge e: G[v]) {
          int to = e.to();
          Cost cost = e.cost();
          if (ds[to] > ds[v] + cost) {
            ds[to] = ds[v] + cost;
            bs[to] = v;
            Q.emplace(to, ds[to]);
          }
        }
      }
    }

    Cost operator[](int k) {
      return ds.at(k);
    }

    vector<int> restore(int to) {
      vector<int> res;
      if (bs[to] == -1) {
        res.emplace_back(to);
        return res;
      }
      while (to != -1) {
        res.emplace_back(to);
        to = bs[to];
      }
      reverse(res.begin(), res.end());
      return res;
    }
  };
} // namespace matumoto

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/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.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/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.11.4/x64/lib/python3.11/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: graph-type.hpp: line -1: no such header

Back to top page