O(ElogV)ダイクストラのテンプレ
O(ElogV)ダイクストラのテンプレ
#include <queue> #include <vector> #include <functional> #include <utility> #include <algorithm> #include <iterator> using COST_T = uint32_t; constexpr uint32_t N_MAX = 変える; constexpr COST_T INF = 変える;//std::numeric_limits<double>::infinity() #if defined(_MSC_VER) && defined(_DEBUG) static_assert(false, "リリースでコンパイルしないと遅いよ!!"); #endif struct edge { uint32_t to; COST_T cost; edge() {} edge(uint32_t to_, COST_T cost_) :to(to_), cost(cost_) {} }; std::vector<edge> graph[N_MAX]; //O(ElogV)ダイクストラ COST_T D[N_MAX]; void Dijkstra(uint32_t s) { using P = std::pair<COST_T, uint32_t>;//cost pos std::priority_queue<P, std::vector<P>, std::greater<P> > que; std::fill(std::begin(D), std::end(D), INF); D[s] = 0; que.emplace(0, s); while (!que.empty()) { auto p = que.top(); que.pop(); const auto& nowpos = p.second; const auto& nowcost = p.first; if (D[nowpos] < nowcost) { continue; } for (const auto& e : graph[nowpos]) { auto cost = nowcost + e.cost; if (cost < D[e.to]) { D[e.to] = cost; que.emplace(cost, e.to); } } } }
使用例
Dijkstra(0);