競プロ思考録

JOI 2013-本選3

現代的な屋敷 | Aizu Online Judge

概要

横Mマス×縦Nマスの格子があり、(1, 1)から(M, N)へ移動したい。
隣のマスにはコスト1で移動できるが、縦移動しかできないときと横移動しかできないときがある。最初は縦移動しかできず、K個のマスにおいてコスト1でどちらができるのかの切り替えができる。
入力はN, M, KとK個のマスの座標。出力は(1, 1)から(M, N)まで移動するのにかかるコスト。移動できない場合は-1。

考察

(1, i)にはi-1で辿り着ける。
DPか？いやdp[100000][100000]は無理そう
(M, N)のスイッチは押す必要なし
スイッチのない部屋はただの経由地点、スイッチからスイッチへと動けば良い→スイッチを頂点としたグラフ？
スイッチのあるマスでは、1.スイッチを押さず進む、2.コスト1でスイッチを押して向きを変えて進む、がある

実装

K個のスイッチのあるマスにスタートとゴールのマスを加えたK+2個のマスそれぞれについて縦移動ができる状態のとき、横移動ができる状態のときの2パターンをもつ。
すなわち、頂点1〜K+2を縦移動ができるときの頂点、頂点K+3〜2K+4を横移動ができるときの頂点とする。なおK, 2K+3がスタート、K+1, 2K+4がゴールのマス。他はスイッチ。
次に、x座標が同じ頂点をy座標でソートし、隣り合う頂点に2頂点間の距離をコストとする辺を張る。y座標が同じ頂点についても同様にする。また頂点iとi+K+2の間にもコスト1の辺を張る。
ゴールにスイッチがある場合があるが、ゴールのスイッチは押す必要がないので常にあるものとして良い。一方スタートにスイッチがある場合は、頂点Kと2K+3の間に辺を張らない。
後は、ダイクストラ法を用いて頂点KからK+1までの距離と頂点Kから2K+4までの距離を求め、その最小値を出力する。最小値がINFであれば-1を出力する。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int n, m, k;
typedef pair<long long int, int> P;
vector<P> x[100010], y[100010];
vector<P> g[400010];
long long int INF = 1e18;
bool f;
long long int d[400010];
priority_queue<P, vector<P>, greater<P> > q;

int main(){
	scanf("%d %d %d", &m, &n, &k);
	for(int i=0; i<k; ++i){
		long long int a, b;
		scanf("%lld %lld", &a, &b);
		if((a + b != n + m) || (a + b != 2)){
			x[a].push_back(P(b, i+1));
			y[b].push_back(P(a, i+1));
		}else if(a + b == 2) f = true;
	}
	x[1].push_back(P(1, k+1));
	y[1].push_back(P(1, k+1));
	x[m].push_back(P(n, k+2));
	y[n].push_back(P(m, k+2));

	for(int i=1; i<=m; ++i){
		sort(x[i].begin(), x[i].end());
		for(int j=0; j+1<x[i].size(); ++j){
			g[x[i][j].second].push_back(P(x[i][j+1].first-x[i][j].first, x[i][j+1].second));
			g[x[i][j+1].second].push_back(P(x[i][j+1].first-x[i][j].first, x[i][j].second));
		}
	}

	for(int i=1; i<=n; ++i){
		sort(y[i].begin(), y[i].end());
		for(int j=0; j+1<y[i].size(); ++j){
			g[y[i][j].second+k+2].push_back(P(y[i][j+1].first-y[i][j].first, y[i][j+1].second+k+2));
			g[y[i][j+1].second+k+2].push_back(P(y[i][j+1].first-y[i][j].first, y[i][j].second+k+2));
		}
	}

	for(int i=1; i<=k; ++i){
		g[i].push_back(P(1, i+k+2));
		g[i+k+2].push_back(P(1, i));
	}
	if(f){
		g[k+1].push_back(P(1, 2*k+3));
		g[2*k+3].push_back(P(1, k+1));
	}
	g[k+2].push_back(P(1, 2*k+4));
	g[2*k+4].push_back(P(1, k+2));

	fill(d+1, d+2*k+5, INF);
	d[k+1] = 0;
	if(f) d[2*k+3] = 1;
	q.push(P(0, k+1));
	while(!q.empty()){
		P p = q.top(); q.pop();
		int v = p.second;
		if(d[v] < p.first) continue;
		for(int i=0; i<g[v].size(); ++i){
			if(d[g[v][i].second] > d[v] + g[v][i].first){
				d[g[v][i].second] = d[v] + g[v][i].first;
				q.push(P(d[g[v][i].second], g[v][i].second));
			}
		}
	}
	long long int ans = min(d[k+2], d[2*k+4]);
	if(ans == INF) printf("-1\n");
	else printf("%lld\n", ans);
}