AtCoder

典型アルゴリズム問題集 D問題(単一始点最短経路問題)を解く

AtCoder_Typical_algorithm

AtCoder で公開されている「典型アルゴリズム問題集」のD問題をC++で解いてみました。

D問題 単一始点最短経路問題

問題はリンク先をご覧ください。

D 単一始点最短経路問題

グラフの始点から、すべての終点への最小移動距離を求めます。

解答案

この問題は、頂点間の移動時間(コスト) $c_i$ は、0以上の整数で与えられます。この場合は、ダイクストラ法(Dijkstra’s algorithm)が使えます。基本的な考え方は以下です。

  • 頂点とコストを組にして、キューを使って処理する。
  • コストが小さい順番に処理する。このため、優先度付きキューを使う場合が多くなります。

注)コストが負の値となる場合は、ベルマン-フォード法(Bellman–Ford algorithm)を使う必要があります。この記事では紹介しません。

C++ プログラム例

重み付きグラフの定番コードと考えることができます。グラフが重み付きになるため、頂点に加えて、コストも管理します(構造体 Edge)。

  • 上でも述べましたが、優先度付きキューを使います(30行目)。
  • キューの初期値として、始点(頂点0)を格納します(31、32行目)。
  • キューが空になるまで、コストが小さい順に処理します(34ー45行目)。なお、37行目の確認が抜けていると、時間がかかる場合があります。
  • dist[n-1]が求める解答になります。

以下が、C++プログラムとなります。

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef long long int ll;
#define INF (1LL << 60)
typedef pair<ll, int> P;
struct Edge {
	int to;
	ll weight;
	Edge() { }
	Edge(int t, ll w) : to(t), weight(w) { }
};

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<Edge>> G(n);
	for (int i = 0; i < m; ++i) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		G[u].push_back(Edge(v, c));
	}

	vector<ll> dist(n, INF);
	priority_queue<P, vector<P>, greater<P>> que;
	dist[0] = 0;
	que.push(P(0, 0));
	while (!que.empty()) {
		P p = que.top();
		que.pop();
		int now = p.second;
		if (dist[now] < p.first) {
			continue;
		}
		for (auto next_v : G[now]) {
			if (dist[next_v.to] > dist[now] + next_v.weight) {
				dist[next_v.to] = dist[now] + next_v.weight;
				que.push(P(dist[next_v.to], next_v.to));
			}
		}
	}

	cout << dist[n - 1] << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

最後に

何回か紹介したダイクストラ法の復習ができました。ある意味貪欲法ですが、応用範囲が広いアルゴリズムだと考えています。

この問題集は、わたくしには、ちょうど良い難易度でした。引き続き解答案を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA