Problem:


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

全時空統一ディメンション・スゴロク・トーナメント。500 兆人を超える参加者の中から、ただ１人
のスゴロク絶対王者を決定するその大会に、あなたは２１世紀の地球代表として参加している。

今あなたが挑戦している課題は、自分自身をコマとした１次元スゴロク。端のスタートマスから出発
して、１から６までの目が一つずつ書かれた巨大な６面ダイスを振って出た目の数だけ進むことを繰
り返す、あなたもよく知っている形式のスゴロクだ。スタートマスとは反対の端にあるゴールマスに
止まるとゴールとなる。もちろん、ゴールするまでにサイコロを振った回数が少なければ少ないほど
良い成績となる。

マスの中には特殊な効果を持ったマス「○マス進む」と「○マス戻る」が存在し、そこに止まってし
まうと、指定されたマス数だけ進む、もしくは戻らなければならない。マスの効果で動いた結果、ふ
たたび効果のあるマスに止まった場合は、続けて指示どおりに移動する。

しかし、これは一筋縄では攻略できない時空スゴロクだ。恐るべきことに、たとえば「３マス進む」
の３マス先に「３マス戻る」が置かれていることもありうる。このようなマスに止まり、マスの効果
で無限ループに陥ってしまった場合は、永遠にマスを往復し続けなければならない。

だが幸いなことに、あなたの身体には、望んだ事象を全事象に変えることのできる異能『確率湾曲』
が宿っている。この能力を使えば、サイコロの出目を自由に操ることも可能。このアドバンテージを
活かして、無限ループに陥らないようにしながら進んでいくとき、ゴールするまでにサイコロを振る
回数の最小値はいくつになるだろうか。

Input

N

p1

p2

.

.

.

pN

入力の１行目には、整数 N（3 ≤ N ≤ 100,000）が書かれている。これは、スゴロクのマス数をあらわす。マスには1 番からN 番までの番号がふられている。スタートのマスが1 番で、それからスタートに近い順に2 番、3 番、……、N - 1 番と続き、ゴールのマスがN 番である。i 番のマスでサイコロを振ってj の目が出たら、i + j 番のマスへと移動する。ただし、もしもi + j がN を超えていたら、余った数だけ戻ったりはせず、ゴールしたとみなされる。

続くN 行には、整数 pi（-100,000 ≤ pi ≤ 100,000）が書かれている。1 ＋ i 行目に書かれた整数 pi
は、i 番のマスに書かれている指示をあらわす。pi > 0 ならば「pi マス進む」、pi < 0 ならば「-pi マス戻る」であり、pi = 0 ならばそのマスには何の効果もない。p1 とpN は必ず0 である。マスの効果で、スタートより前やゴールより後に移動しろと指示されることはない。

なお、与えられるスゴロクは、ゴールすることが可能であると仮定してよい。

Output

ゴールするまでにサイコロを振る回数の最小値を出力せよ。

Sample Input 1

11
0
0
-2
0
-4
1
-1
2
0
0
0

Sample Output 1

3

Sample Input 2

12
0
0
7
0
2
0
0
3
-6
-2
1
0

Sample Output 2

1

Sample Input 3

8
0
4
-1
1
-2
-2
0
0

Sample Output 3

2



Sample input:
11
0
0
-2
0
-4
1
-1
2
0
0
0


Sample output:
3

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
used = [False]*N
for i in xrange(N):
        if used[i]: continue
        seq = []
        for loop in xrange(10):
            if i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                used[i] = True
                for j in seq: to[j] = i
                break
            else:
                seq.append(i)
                used[i] = True
                i += p[i]
ans = i = 0
while i < N-1:
    nxt = 0
    for j in xrange(i+1,min(N,i+7)):
        nxt = max(nxt, to[j])
    i = nxt
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N+6)]
used = [False]*N
for i in xrange(N):
        if used[i]: continue
        seq = []
        for loop in xrange(10):
            used[i] = True            
            if i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.append(i)
                i += p[i]
                
ans = i = 0
while i < N-1:
    nxt = 0
    for j in xrange(i+1,i+7):
        nxt = max(nxt, to[j])
    i = nxt
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N+6)]
used = [False]*N
for i in xrange(N):
        if used[i]: continue
        seq = []
        while 1:
            used[i] = True            
            if i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.append(i)
                i += p[i]
                
ans = i = 0
while i < N-1:
    nxt = 0
    for j in xrange(i+1,i+7):
        nxt = max(nxt, to[j])
    i = nxt
    ans += 1
print ans

Submission status: Wrong Answer

Solution code:
inf = 1 << 28
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N+6)]
used = [False]*N
for i in xrange(N):
        if used[i]: continue
        seq = set([])
        while 1:
            used[i] = True            
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                
dp = [inf]*(N+6)
dp[0] = 0
for i in xrange(N):
    for j in xrange(1,7):
        dp[to[i+j]] = min(dp[to[i+j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N+6)]
used = [False]*N
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                
dp = [inf]*(N+6)
dp[0] = 0
for i in xrange(N):
    for j in xrange(1,7):
        dp[to[i+j]] = min(dp[to[i+j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]

dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if p[i] < 0: continue
    for j in xrange(i+1,min(N,i+7)):
        if p[j] < 0: continue
        dp[j+p[j]] = min(dp[j+p[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    for j in xrange(i+1,min(N,i+7)):
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if dp[i] == inf: continue
    for j in xrange(i+1,min(N,i+7)):
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if dp[i] == inf: continue
    for j in xrange(i+1,min(N,i+7)):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if dp[i] == inf: continue
    for j in xrange(i+1,min(N,i+7)):
        if to[j] < j: continue
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if to[i] != i:
                for j in seq: to[j] = to[i]
                break
            elif i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if dp[i] == inf: continue
    for j in xrange(i+1,min(N,i+7)):
        if to[j] < j: continue
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Wrong Answer

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if to[i] != i:
                for j in seq: to[j] = to[i]
                break
            elif i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]

visited = [False]*N
visited[0] = True
que = [[0,0]]
while 1:
    s,step = que.pop(0)
    for i in xrange(1,6):
        if i+s >= N-1:
            print step
            exit()
        if to[i+s] > -1 and not visited[i+s]:
            visited[i+s] = True
            que.append([to[i+s],step+1])

Submission status: Accepted

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if to[i] != i:
                for j in seq: to[j] = to[i]
                break
            elif i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]

visited = [False]*N
visited[0] = True
que = [[0,0]]
while 1:
    cur,step = que.pop(0)
    if cur == N-1:
        print step
        break
    for nxt in range(cur+1,min(N,cur+7)):
        if to[nxt] > 0 and not visited[to[nxt]]:
            visited[to[nxt]] = True
            que.append([to[nxt], step+1])

Submission status: Accepted

Solution code:
import Queue, sys
INF = 10**9+7
n = input()
p = []
for i in xrange(n):
    p.append(int(raw_input()))
dist = [10**7] * n
calc = [-1] * n
used = [False] * n
que = Queue.PriorityQueue()
que.put((0, 0))
dist[0] = 0
while not que.empty():
    co, v = que.get()
    if dist[v] < co:
        continue
    for k in xrange(1, 7):
        go = v+k
        if go>=n:
            break
        if p[go] != 0:
            if calc[go]==-1:
                path = []
                while True:
                    if p[go]==0:
                        break
                    if calc[go]!=-1:
                        go = calc[go]
                        break
                    if used[go]:
                        go = INF
                        break
                    used[go] = True
                    path.append(go)
                    go += p[go]
                for e in path:
                    calc[e] = go
            else:
                go = calc[go]
            if go==INF:
                continue
        if go==n-1:
            print dist[v]+1
            exit(0)
        if dist[v] + 1 < dist[go]:
            dist[go] = dist[v] + 1
            que.put((dist[go], go))

Submission status: Accepted

Solution code:
import Queue
INF = 10**9
n = input()
p = [i+int(raw_input()) for i in xrange(n)]

used = [0] * n
idx = 0
for i in xrange(n):
    if p[i]!=i:
        path = []
        go = i
        idx += 1
        while go!=INF and p[go]!=go:
            if used[go]==idx:
                go = INF
                break
            used[go] = idx
            path.append(go)
            go = p[go]
        for e in path:
            p[e] = go

dist = [INF] * n
que = Queue.Queue()
que.put(0)
dist[0] = 0
while not que.empty():
    v = que.get()
    for k in xrange(1, min(7, n-v)):
        go = p[v+k]
        if go==n-1:
            print dist[v]+1
            exit(0)
        if go!=INF and dist[v] + 1 < dist[go]:
            dist[go] = dist[v] + 1
            que.put(go)

Submission status: Accepted

Solution code:
import heapq

N = int(raw_input())
mins = [10**9] * (N+1)
mins[0] = 0
maps = [0] * (N+1)
maps[0] = 0
for i in xrange(N):
  maps[i+1] = int(raw_input())
h = []
for i in xrange(1, 7):
  heapq.heappush(h, [1, i+1])
while h:
  check = heapq.heappop(h)
  if N < check[1] or mins[check[1]] <= check[0]: continue
  mins[check[1]] = check[0]
  if maps[check[1]] == 0:
    for i in xrange(1, 7):
      heapq.heappush(h, [check[0]+1, check[1]+i])
  else:
    heapq.heappush(h, [check[0], check[1]+maps[check[1]]])
print mins[N]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
0-1 BFS
"""



from collections import deque
N = int(input())
INF = 10**9

A = [int(input()) for _ in range(N)] + [0]*6
B = [INF]*(N+6)
B[0] = 0

Q = deque([[0, 0]])

while Q:
    x, y = Q.popleft()
    if x >= N-1:
        print(y)
        break
    if B[x] < y:
        continue

    if A[x] == 0:
        for i in range(1, 7):
            if y + 1 < B[x+i]:
                B[x+i] = y + 1
                Q.append([x+i, y+1])
    else:
        if y < B[x+A[x]]:
            B[x+A[x]] = y
            Q.appendleft([x+A[x], y])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()

        a = [I() for _ in range(n)]
        e = collections.defaultdict(list)
        for i in range(n):
            if a[i] == 0:
                for j in range(1,7):
                    e[i].append((i+j, 1))
            else:
                e[i].append((i+a[i], 0))

        def search(s):
            d = collections.defaultdict(lambda: inf)
            d[s] = 0
            q = []
            heapq.heappush(q, (0, s))
            v = collections.defaultdict(bool)
            while len(q):
                k, u = heapq.heappop(q)
                if v[u]:
                    continue
                v[u] = True
                if u == n-1:
                    return k

                for uv, ud in e[u]:
                    if v[uv]:
                        continue
                    vd = k + ud
                    if d[uv] > vd:
                        d[uv] = vd
                        heapq.heappush(q, (vd, uv))

            return -1

        rr.append(search(0))
        break

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
sys.setrecursionlimit(1000000)
INF = 10 ** 20

def bfs(x):
  if visited[x] == 2:
    return None
  if visited[x] == 1:
    return edges[x]
  if plst[x] == 0:
    edges[x] = x
    visited[x] = 1
    return x

  visited[x] = 2
  ret = bfs(x + plst[x])
  if ret != None:
    edges[x] = ret
    visited[x] = 1
  return ret

def search():
  cost = [INF] * n
  cost[0] = 0
  que = []
  heappush(que, (0, 0))
  while que:
    score, pos = heappop(que)
    for dice in range(1, 7):
      new_pos = pos + dice
      if new_pos >= n - 1:
        print(score + 1)
        return
      
      if edges[new_pos] == None:
        continue
      
      new_pos = edges[new_pos]
      if new_pos >= n - 1:
        print(score + 1)
        return
      
      if cost[new_pos] > score + 1:
        cost[new_pos] = score + 1
        heappush(que, (score + 1, new_pos))
  else:
    print("Miss!!")

n = int(input())
plst = [int(input()) for _ in range(n)]
edges = [None for _ in range(n)]
visited = [0] * n
for i in range(n):
  bfs(i)
search()

Submission status: Runtime Error

Solution code:
inf = 1 << 28
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N+6)]
used = [False]*N
for i in xrange(N):
        if used[i]: continue
        seq = []
        while 1:
            used[i] = True            
            if i in seq:
                for j in seq: to[j] = 0
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.append(i)
                i += p[i]
dp = [inf]*(N+6)
dp[0] = 0
for i in xrange(N):
    for j in xrange(1,7):
        dp[to[i+j]] = min(dp[to[i+j]], dp[i]+1)
print dp[N-1]

Submission status: Runtime Error

Solution code:
inf = 10**9
N = int(raw_input())
p = [int(raw_input()) for i in xrange(N)]
to = [i for i in xrange(N)]
for i in xrange(N):
        if to[i] != i: continue
        seq = set([])
        while 1:
            if to[i] != i:
                for j in seq: to[j] = to[i]
            elif i in seq:
                for j in seq: to[j] = -1
                break
            elif p[i] == 0:
                for j in seq: to[j] = i
                break
            else:
                seq.add(i)
                i += p[i]
                 
dp = [inf]*N
dp[0] = 0
for i in xrange(N):
    if dp[i] == inf: continue
    for j in xrange(i+1,min(N,i+7)):
        if to[j] < j: continue
        dp[to[j]] = min(dp[to[j]], dp[i]+1)
print dp[N-1]

Submission status: Runtime Error

Solution code:
import Queue
n = input()
p = []
for i in xrange(n):
    p.append(int(raw_input()))
dist = [10**7] * n
mark = [0]*n
que = Queue.PriorityQueue()
que.put((0, 0))
dist[0] = 0
idx = 0
while not que.empty():
    co, v = que.get()
    if dist[v] < co:
        continue
    for k in xrange(1, 7):
        idx += 1
        go = v+k
        while p[go]:
            go += p[go]
            if mark[go] == idx:
                go = -1
                break
            mark[go] = idx
        if go==-1:
            continue
        if go==n-1:
            print dist[v] + 1
            exit(0)
        if dist[v] + 1 < dist[go]:
            dist[go] = dist[v] + 1
            que.put((dist[go], go))

Submission status: Runtime Error

Solution code:
import Queue
INF = 10**9+7
n = input()
p = []
for i in xrange(n):
    p.append(int(raw_input()))
dist = [10**7] * n
calc = [-1] * n
used = [False] * n
que = Queue.PriorityQueue()
que.put((0, 0))
dist[0] = 0
def dfs(pos, calc, used, f):
    if p[pos]==0:
        return pos
    if calc[pos]!=-1:
        return calc[pos]
    if used[pos]:
        return INF
    used[pos] = True
    calc[pos] = dfs(pos+p[pos], calc, used, p[pos])
    used[pos] = False
    return calc[pos]
while not que.empty():
    co, v = que.get()
    if dist[v] < co:
        continue
    for k in xrange(1, 7):
        go = v+k
        if go>=n:
            break
        if p[go] != 0:
            if calc[go]==-1:
                dfs(go, calc, used, 0)
            if calc[go]==INF:
                continue
            go = calc[go]
        if go==n-1:
            print dist[v]+1
            exit(0)
        if dist[v] + 1 < dist[go]:
            dist[go] = dist[v] + 1
            que.put((dist[go], go))

Submission status: Runtime Error

Solution code:
import Queue, sys
INF = 10**9+7
n = input()
p = []
for i in xrange(n):
    p.append(int(raw_input()))
dist = [10**7] * n
calc = [-1] * n
used = [False] * n
que = Queue.PriorityQueue()
que.put((0, 0))
dist[0] = 0
sys.setrecursionlimit(10**5+7)
def dfs(pos, calc, used, f):
    if p[pos]==0:
        return pos
    if calc[pos]!=-1:
        return calc[pos]
    if used[pos]:
        return INF
    used[pos] = True
    calc[pos] = dfs(pos+p[pos], calc, used, p[pos])
    used[pos] = False
    return calc[pos]
while not que.empty():
    co, v = que.get()
    if dist[v] < co:
        continue
    for k in xrange(1, 7):
        go = v+k
        if go>=n:
            break
        if p[go] != 0:
            if calc[go]==-1:
                dfs(go, calc, used, 0)
            if calc[go]==INF:
                continue
            go = calc[go]
        if go==n-1:
            print dist[v]+1
            exit(0)
        if dist[v] + 1 < dist[go]:
            dist[go] = dist[v] + 1
            que.put((dist[go], go))

Submission status: Runtime Error

Solution code:
import sys
import queue
ISLOOP = 999999999

def next_position(sugoroku, visited, curr, edges):
    if edges[curr] != -1:
        return edges[curr]
    if curr in visited:
        return ISLOOP
    if sugoroku[curr] == 0:
        return curr
    # ?????????????????§?????????????????????????????´???????????????????§????????????¨????????????????????¨????????????
    visited.append( curr )
    edges[curr] = next_position(sugoroku, visited, curr + sugoroku[curr], edges)
    return edges[curr]


def main():
    n = int(input())
    sugoroku = []
    for i in range(n):
        sugoroku.append( int(sys.stdin.readline()) )

    # ????????????????????????????????????????¨??????????
    edges = [-1] * n
    for i in range(n):
        visited = []
        edges[i] = next_position(sugoroku, visited, i, edges)

    visited = [False] * n
    visited[0] = True
    q = queue.Queue()
    q.put( (0, 0) )

    ans = -1
    while not q.empty():
        curr,step = q.get()
        for k in range(1,7):
            if curr + k >= n - 1:
                ans = step + 1
                break
            j = edges[curr + k]
            if j == n - 1:
                ans = step + 1
                break
            if j == ISLOOP or visited[j]:
                continue
            q.put( (j, step + 1) )
            visited[j] = True
        if ans != -1:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import queue
ISLOOP = 999999999

def next_position(n, sugoroku, visited, curr, edges):
    if edges[curr] != -1:
        return edges[curr]
    if curr in visited:
        return ISLOOP
    if sugoroku[curr] == 0:
        return curr
    visited.append( curr )
    edges[curr] = next_position(n, sugoroku, visited, max(0, min(n - 1, curr + sugoroku[curr])), edges)
    return edges[curr]


def main():
    n = int(input())
    sugoroku = []
    for i in range(n):
        sugoroku.append( int(sys.stdin.readline()) )

    # ????????????????????????????????????????¨??????????
    edges = [-1] * n
    for i in range(n):
        visited = []
        edges[i] = next_position(n, sugoroku, visited, i, edges)

    visited = [False] * n
    visited[0] = True
    q = queue.Queue()
    q.put( (0, 0) )

    ans = -1
    while not q.empty():
        curr,step = q.get()
        for k in range(1,7):
            if curr + k >= n - 1:
                ans = step + 1
                break
            j = edges[curr + k]
            if j == n - 1:
                ans = step + 1
                break
            if j == ISLOOP or visited[j]:
                continue
            q.put( (j, step + 1) )
            visited[j] = True
        if ans != -1:
            break

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
import queue
ISLOOP = 999999999

sys.setrecursionlimit(100000)

def next_position(n, sugoroku, visited, curr, edges):
    if edges[curr] != -1:
        return edges[curr]
    if curr in visited:
        return ISLOOP
    if sugoroku[curr] == 0:
        return curr
    # ?????????????????§?????????????????????????????´???????????????????§????????????¨????????????????????¨????????????
    visited.append( curr )
    edges[curr] = next_position(n, sugoroku, visited, max(0, min(n - 1, curr + sugoroku[curr])), edges)
    return edges[curr]


def main():
    n = int(input())
    sugoroku = []
    for i in range(n):
        sugoroku.append( int(sys.stdin.readline()) )

    # ????????????????????????????????????????¨??????????
    edges = [-1] * n
    for i in range(n):
        visited = []
        edges[i] = next_position(n, sugoroku, visited, i, edges)

    visited = [False] * n
    visited[0] = True
    q = queue.Queue()
    q.put( (0, 0) )

    ans = -1
    while not q.empty():
        curr,step = q.get()
        for k in range(1,7):
            if curr + k >= n - 1:
                ans = step + 1
                break
            j = edges[curr + k]
            if j == n - 1:
                ans = step + 1
                break
            if j == ISLOOP or visited[j]:
                continue
            q.put( (j, step + 1) )
            visited[j] = True
        if ans != -1:
            break

    print(ans)

if __name__ == "__main__":
    main()