ARC056 B 駐車場(ダイクストラ法)

シェアする

  • このエントリーをはてなブックマークに追加

こんばんは。

先日からCODE VS for STUDENTの予選が開始され、ブログの更新ができませんでした。

というのも、CODE VSのクライアントが上手く動かなくて悪戦苦闘していたり(ルールテキストに普通に「Java 1.8.0_102じゃないとダメだよ」と書いていました)、バグがなかなか取れずに苦しんだり(今も)。

本日もまさにCODE VSのためのバグ取りなどに専念しており、競プロの問題を解いていないのですが、少し前に解いたARC056のB問題「駐車場」について書きたいと思います。

この問題は、グラフ構造とスタート地点Sが与えられ、「開始ノードからノードiに行けるときはノードiを封鎖(通行不可能に)し、行けないときは諦める」という操作をiが小さい順に行い、「ノードiに行けたやつ」の数字を全て出力するという問題です。

したがって、「開始ノードからそのノードに行くためには、そのノードの番号よりも小さい番号のノードを必ず通らなければいけない」というようなノードは到達不可能となります。そのノードへのチャレンジを行う時点で、それより小さい番号のノードは全て封鎖されているからです。

ということは、全ノードについて「そこに行くために通らなければならない最小ノード番号」を記録すると、「その番号がノード番号よりも小さい場合はNG、小さくない場合はOK」という判定が可能になります。

これを実装します。

ダイクストラ法もどき

ダイクストラ法とは、グラフの「単一始点最短経路問題」を解くためのアルゴリズムです。辺にコスト(重み)があるグラフ構造とスタート地点があたえられて、「各ノードへ行くまでの最小コスト」を求めるアルゴリズムということです。各ノードに「そこに最短経路で行くときの、直前に通ったノード」を記録しておくことで、最小コストだけでなく最短経路も得られます。

ダイクストラ法では、以下の手順で最小コストを求めます。

1. スタート地点のコストを0にする。他の点のコストは∞にしておく(実装上はintの最大値など)
2. コストが確定していない点の中からコストが最小の点を一つ選ぶ(点vとする)。全ての点のコストが確定していれば終了する
3. 点vのコストを確定させる
4. 点vの隣の点(コストが確定した点を除く)すべてについて、「点vのコスト+点vとその点をつなぐ辺のコスト」がその点の現在のコストよりも小さかったら、コストを更新する(より効率的な経路を発見した)。
5. 2.に戻る

2.において、暫定コストが最小の点を選ぶときに「優先度付きキュー(プライオリティキュー)」というデータ構造を選ぶと、O(logV)で点を選べます。

今回の問題では、ノードにコストとして「そこに到達するまでに通ったノードの最小番号」を設定し、「大きいほど良い」というルールで計算していきます。

今回は、ノード5, 3, 4, 2を通ってノード2に到達した場合のノード2のコストを2とする実装を行いました(3ではなく、到達したノード自身の番号も含めた最小値。つまり、少なくとも自身のノード番号以下になる)。

つまり、以下の流れになります。

1. スタート地点のコストをスタートの番号にする。ほかは0にする
2. コストが確定していない点の中からコストが最大の点を一つ選ぶ(点vとする)。全ての点のコストが確定していれば終了する
3. 点vのコストを確定させる
4. 点vの隣の点(コストが確定した点を除く)すべてについて、点vのコストがその点のコストよりも大きければ、その点のコストをその点のノード番号にし、小さければmax(その点の暫定コスト, 点vのコスト)にする。
5. 2.に戻る

こうすると、全てのノードについて「そのノードに到達するまでに訪れたノードの最小番号」を計算することができるので、全ノードについて「コスト=ノード番号」ならその番号を出力すればいいのです(内部で0-indexedにしていれば、ノード番号+1を出力)。

以上を実現したのが以下のC++コードです。

#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include

<map>
 
using namespace std;
 
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
 
typedef long long ll;
typedef pair<int, int> P;
#define mp make_pair
 
 
const int MOD = 1000000007;
 
void solve(vector<int> graph[], int start, vector<int> &cost, int N) {
	vector<int> prev(N);
	vector<bool> visited(N);
	priority_queue

<P> Q;
 
	cost[start] = start;
	
	Q.push(mp(start, start));	// (cost, index)
	
	while (!Q.empty()) {
		P pos = Q.top();	// コスト最大の点を取得
		Q.pop();	// 取得した点を削除
		rep(i, graph[pos.second].size()) {
			if (cost[graph[pos.second][i]] < min(graph[pos.second][i], cost[pos.second])) {
				cost[graph[pos.second][i]] = min(graph[pos.second][i], cost[pos.second]);
				Q.push(mp(cost[graph[pos.second][i]], graph[pos.second][i]));
			}
		}
	}
}
 
vector<int> graph[200000];
 
int main() {
	int N, M, S;
	
	cin >> N >> M >> S;
 
	vector<int> cost(N);
 
	rep(i, M) {
		int u, v;
		cin >> u >> v;
		graph[u - 1].push_back(v - 1);	// グラフの接続情報を記録
		graph[v - 1].push_back(u - 1);	// 反対向きも記録
	}
 
	solve(graph, S - 1, cost, N);
 
 
	rep(i, N) {
		if (cost[i] >= i) {
			cout << i + 1 << endl;
		}
	}
 
	return 0;
}
スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする