KUPC 2014 H - 自転車走

問題

日本語なので本文参照（http://kupc2014.contest.atcoder.jp/tasks/kupc2014_h）

方針

全部メモ化するダイクストラの嘘解法を適当に時間に間に合うように打ち切ったら通ってしまった。

ソースコード

int n, l, w;
int a[100000], b[100000];
bool v[100000];

vector<vi> e;

inline int get(int x){
	int i = lower_bound(b, b + n, x) - b;
	if(i >= n || a[i] > x) return -1;
	return i;
}

int main(){
	
	cin >> n >> l >> w;
	rep(i, n) cin >> a[i] >> b[i];
	e.resize(n);
	
	rep(i, n){
		rep(it, 4){
			int pos = it & 1 ? a[i] : b[i];
			pos += it & 2 ? w : -w;
			
			pos = get(pos);
			if(pos < 0) continue;
			if(i < pos) e[i].pb(pos);
			if(i > pos) e[pos].pb(i);
		}
	}
	rep(i, n){
		sort(all(e[i]));
		e[i].erase(unique(all(e[i])), e[i].end());
	}
	
	set<pi> s;
	priority_queue<pair<pi, int> > q; //jump, node, from left
	q.push(mp(mp(0, 0), 0));
	
	vi cnt(n);
	
	while(!q.empty()){
		int jmp = -q.top().first.first;
		int cur = q.top().first.second;
		int pos = -q.top().second;
		q.pop();
		
		if(s.count(mp(jmp, cur))) continue;
		s.insert(mp(jmp, cur));
		
		if(++cnt[cur] > 20) continue;
		
		if(cur == n - 1){
			cout << jmp << endl;
			return 0;
		}
		
		rep(i, e[cur].size()){
			int to = e[cur][i];
			int L = max(pos, a[to] - w);
			int R = min(b[cur], b[to] - w);
			
			if(L <= R && !s.count(mp(jmp + 1, to)))
			q.push(mp(mp(-jmp - 1, to), -(L + w)));
		}
	}
	
	cout << -1 << endl;
	
	return 0;
}