fork download 
  1. # your code goes here
  2. import sys
  3. from collections import deque
  4. input = sys.stdin.readline
  5.  
  6. stair = dict()
  7. cnt = int(input())
  8. result = [0] * (cnt+1)
  9. visited = [0]*301
  10. for i in range(1,cnt+1):
  11.     stair[i] = int(input())
  12.  
  13. def bfs(s,c,w):
  14.     q = deque([(s,c,w)])
  15.  
  16.     while q:
  17.         t,c,w = q.popleft()
  18.         if c == 3:
  19.             continue
  20.         if t == cnt:
  21.             result.append(visited[t])
  22.  
  23.         if c < 2:
  24.             if t+1 <= cnt:
  25.                 if visited[t+1] != 0:
  26.                     if visited[t+1] < w + stair[t+1]:
  27.                         visited[t+1] = w + stair[t+1]
  28.                         q.append((t+1,c+1,visited[t+1]))
  29.                 else:
  30.                     visited[t+1] = w + stair[t+1]
  31.                     q.append((t+1,c+1,visited[t+1]))
  32.         if t+2 <= cnt:
  33.             if visited[t+2] != 0 :
  34.                 if visited[t+2] < w + stair[t+2]:
  35.                     visited[t+2] = w + stair[t+2]
  36.                     q.append((t+2,1,visited[t+2]))
  37.             else:
  38.                 visited[t+2] = w + stair[t+2]
  39.                 q.append((t+2,1,visited[t+2]))
  40.     return visited[cnt]
  41.  
  42. if cnt > 1:
  43.     print(bfs(0,0,0))
  44. else:
  45.     print(stair[1])
Success #stdin #stdout 0.03s 9692KB
comments (?)
stdin 
4
1
100
100
1
stdout 
102
https://ideone.com/tqrk4f
language:
Python 3 (python  3.12)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!