AOJ_2332

最短距離を、ループを回しどんどん更新して求めていく。
更新されなくなったら、最短距離が確定する。

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

const int INF = 1 << 21;
const int MAX_N = 100000;

//d[i] := i番目のマスからゴールにつくまで最小の、サイコロを振る回数
int a[MAX_N + 7], d[MAX_N + 7];
int N;

int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
		scanf("%d", &a[i]);
	fill(d, d + N - 1, INF);
	bool f = true;

	//距離に変更がなければfがfalseになってループ終わり
	while(f){
		f = false;
		for(int i = N - 2; i >= 0; i--){
			if(a[i] != 0){
				//マスの指示がない
				if(d[i] != d[i + a[i]]){
					f = true; //変更した
					d[i] = d[i + a[i]];
				}
			}else{
				//マスに値が書いてある
				int mind = INF;
				for(int j = 1; j <= 6; j++){
					mind = min(mind, d[i + j]);
				}
				if(mind + 1 < d[i]){
					f = true; //変更した
					d[i] = mind + 1;
				}
			}
		}
	}
	printf("%d\n", d[0]);
	return 0;
}