AOJ 2332: Space-Time Sugoroku Road

Problem 3: 時空のスゴロク・ロード

全てのマスに対して、暫定の最短距離を求めるのを繰り返した。蟻本でこんな感じのアルゴリズムを見た記憶がある。たどり着く場所と、そこへの最短距離だけ分かればいい気がするけど、これでも通った。

int p[100000],d[100000];

int main(){
	int i,j,n;
	cin >> n;
	memset(d,-1,sizeof(d));
	d[0] = 0;
	for(i = 0; i < n; i++){
		cin >> p[i];
	}
	int b = 1;
	while(b){
		b = 0;
		for(i = 0; i < n-1; i++){
			if(!p[i] && d[i] != -1){
				for(j = 1; j <= 6; j++){
					int k = i + j;
					int s = i;
					if(k >= n && (d[n-1] == -1 || d[s] + 1 < d[n-1])){
						d[n-1] = d[s] + 1;
						b = 1;
					}else if(d[k] == -1 || d[s] + 1 < d[k]){
						d[k] = d[s] + 1;
						s = k;
						k += p[k];
						b = 1;
						while(d[k] == -1 || d[s] < d[k]){
							d[k] = d[s];
							s = k;
							k += p[k];
						}
					}
				}
			}
		}
	}
	cout << d[n-1] << endl;
	return 0;
}

あと、refiuteさんのコードから適当にバグ取って、速くしたら通りました。