Dijkstra(経路復元付ダイクストラ) (graph/dijkstra.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-05-17 18:10:14+09:00

なにこれ

始点 $s$ から各頂点までの最短距離および最短経路を求める．

コンストラクタ

• dijkstra(path, cost, s)：隣接リスト path，各辺の重み cost，始点 s の無向グラフに対しダイクストラ法を適用する．

メンバ関数

• operator[](idx)：始点 $s$ から頂点 $\mathrm{idx}$ までの最短距離を返す．
• get_path(t)：始点 $s$ から頂点 $t$ までの最短経路を返す．

計算量

頂点数を $n$，辺数を $m$ とする．

• コンストラクタ：$O((n+m)\log n)$
• operator[](idx)：$O(1)$
• get_path(t)：$O(n)$

Depends on

• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Verified with

• test/aoj_GRL_1_A.cpp
• test/yosupo_shortest_path.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "../structure/2d_array.cpp"

template<typename T> struct dijkstra {
	using P = pair<long long, int>;
	const long long inf = (1LL << 62) - 1;

private:
	int n;
	vector<long long> dist;
	vector<int> prev;

public:
	dijkstra(v2d<int> &path, v2d<T> &cost, int s) : n(path.size()), dist(n, inf), prev(n, -1) {
		dist[s] = 0;
		priority_queue<P, vector<P>, greater<P>> q;
		q.emplace(0, s);
		while(not q.empty()) {
			auto [d, x] = q.top();
			q.pop();
			if(d > dist[x]) continue;
			for(int i = 0; i < path[x].size(); i++) {
				int nx = path[x][i];
				long long nd = d + cost[x][i];
				if(nd >= dist[nx]) continue;
				dist[nx] = nd;
				prev[nx] = x;
				q.emplace(nd, nx);
			}
		}
	}

	inline long long operator[](int idx) {
		return dist[idx];
	}

	vector<int> get_path(int t) {
		vector<int> ans;
		for(int x = t; x >= 0; x = prev[x]) ans.emplace_back(x);
		return vector<int>(ans.rbegin(), ans.rend());
	}
};

#line 2 "graph/dijkstra.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#line 2 "structure/2d_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < m.size());
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};
#line 10 "graph/dijkstra.cpp"

template<typename T> struct dijkstra {
	using P = pair<long long, int>;
	const long long inf = (1LL << 62) - 1;

private:
	int n;
	vector<long long> dist;
	vector<int> prev;

public:
	dijkstra(v2d<int> &path, v2d<T> &cost, int s) : n(path.size()), dist(n, inf), prev(n, -1) {
		dist[s] = 0;
		priority_queue<P, vector<P>, greater<P>> q;
		q.emplace(0, s);
		while(not q.empty()) {
			auto [d, x] = q.top();
			q.pop();
			if(d > dist[x]) continue;
			for(int i = 0; i < path[x].size(); i++) {
				int nx = path[x][i];
				long long nd = d + cost[x][i];
				if(nd >= dist[nx]) continue;
				dist[nx] = nd;
				prev[nx] = x;
				q.emplace(nd, nx);
			}
		}
	}

	inline long long operator[](int idx) {
		return dist[idx];
	}

	vector<int> get_path(int t) {
		vector<int> ans;
		for(int x = t; x >= 0; x = prev[x]) ans.emplace_back(x);
		return vector<int>(ans.rbegin(), ans.rend());
	}
};

Back to top page