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; }