Problem:


 ぴょんぴょん川渡り   

問題

ある川で,一方の岸から石の上を次々と飛び移って反対側の岸まで行くという少々危険なゲームがはやっている.

今,図 4-1 のように,石はマス目の上に存在すると考える.行の数は n である. 図 4-1 では n = 5 である.

このゲームでは,一方の岸から始めて,通常のジャンプまたは m 回以下の一行飛ばしのジャンプをして反対側の岸まで渡る.通常のジャンプとは,今いる行の一つ先の行の岸または石のどれかに飛び移ることであり,一行飛ばしのジャンプとは,今いる行の二つ先の行の岸または石のどれかに飛び移ることである.始める岸の一つ先の行は 1 行目,二つ先の行は 2 行目であり,n − 1 行目の二つ先の行,及び n 行目の一つ先の行は反対側の岸であるとする.

さて,このゲームをできるだけ安全に成し遂げるために,ジャンプの危険度というものを考えることにした.それぞれの石には,滑りやすさが定まっている.石から石へ飛び移る際のジャンプの危険度は,通常のジャンプであっても,一行飛ばしのジャンプであっても,

  (今いる石の滑りやすさ + 飛び移る先の石の滑りやすさ)&times;(横の移動距離)

で定める.ただし,横の移動距離とは,列の番号の差である.また,岸から石へ,あるいは石から岸へ飛び移るジャンプの危険度は 0 とする.

入力として n, m,それぞれの石の位置と滑りやすさが与えられたとき,反対側の岸まで到達する際のジャンプの危険度の合計の最小値を求めるプログラムを作成せよ.与えられる入力データは必ず反対側の岸まで到達することができるようになっており,同じマス目に石は 2 個以上存在しない.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

入力の 1 行目には,空白を区切りとして 2 個の整数 n,m が書かれている.これは,行の数と,一行飛ばしのジャンプの許される回数を表す.n,m はそれぞれ 2 ≤ n ≤ 150, 0 ≤ m ≤ (n+1)/2　を満たす.

続く n 行には,それぞれの行にある石の情報が書かれている.i+1 行目 (1 ≤ i ≤ n)には,1 つの整数 ki (0 ≤ ki ≤ 10) と,それに続き 2 &times; ki 個の整数が空白で区切られ書かれている.これらは,始める岸から数えて i 番目の行にある石の情報を表す.

 ki はその行に存在する石の個数を表し,それに続く 2 &times; ki 個の整数については,2 &times; j - 1 個目 (1 ≤ j ≤ ki ) の整数 xi,j はその行の j 個目の石の列の番号を,2 &times; j個目の整数 di,j はその行の j 個目の石の滑りやすさをそれぞれ表す.xi,j ,di,j はそれぞれ 1 ≤ xi,j, di,j ≤1000 を満たす.

採点用データのうち, 配点の 20% 分については, n ≤ 6 を満たし,配点の別の 20%分については, m = 0 を満たす.

n, m がともに 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

 データセットごとに, 反対側の岸まで到達する際のジャンプの危険度の合計の最小値を表す 1 つの整数を1 行に出力する.

例

  図 4-2 において,石に書かれた数字はそれぞれの石の滑りやすさを表すとする.
矢印で示された順番で石を渡るとき,それぞれのジャンプの危険度は,順番に 0,
(2 + 2) &times; 1 = 4,(2 + 1) &times; 1 = 3,(1 + 4) &times; 2 = 10,0 であり,合計は 17 となる.
このとき,ジャンプの危険度の合計は最小となる.
  この例は１つ目の入出力例に対応している.

入出力例

入力例

5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
0 0

出力例

17
40

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5 1
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
5 0
2 1 3 2 2
1 3 2
1 1 7
1 2 1
1 4 4
0 0


Sample output:
17
40

Submission status: Wrong Answer

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    P = []
    K = []
    for i in range(N):
        k, *S = map(int, input().split())
        P.append(list(zip(S[::2], S[1::2])))
        K.append(k)
    INF = 10**18
    memo = {}
    def dfs(i, j, k):
        key = i, j, k
        if key in memo:
            return memo[key]
        if i == N-1:
            return 0
        res = INF
        xi, di = P[i][j]
        for p in range(K[i+1]):
            xj, dj = P[i+1][p]
            res = min(res, dfs(i+1, p, k) + abs(xi - xj)*(di + dj))
        if i+2 < N and k < M:
            for p in range(K[i+2]):
                xj, dj = P[i+2][p]
                res = min(res, dfs(i+2, p, k+2) + abs(xi - xj)*(di + dj))
        memo[key] = res
        return res
    ans = INF
    for i in range(K[0]):
        ans = min(ans, dfs(0, i, 0))
    print(ans)

Submission status: Wrong Answer

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    P = []
    K = []
    for i in range(N):
        k, *S = map(int, input().split())
        P.append(list(zip(S[::2], S[1::2])))
        K.append(k)
    INF = 10**18
    memo = {}
    def dfs(i, j, k):
        key = i, j, k
        if key in memo:
            return memo[key]
        if i == N-1:
            return 0
        res = INF
        xi, di = P[i][j]
        for p in range(K[i+1]):
            xj, dj = P[i+1][p]
            res = min(res, dfs(i+1, p, k) + abs(xi - xj)*(di + dj))
        if i+2 < N and k < M:
            for p in range(K[i+2]):
                xj, dj = P[i+2][p]
                res = min(res, dfs(i+2, p, k+1) + abs(xi - xj)*(di + dj))
        memo[key] = res
        return res
    ans = INF
    for i in range(K[0]):
        ans = min(ans, dfs(0, i, 0))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
INF = 10 ** 20
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  lines = []
  klst = []
  acc = 1
  for _ in range(n):
    lst = list(map(int, input().split()))
    k = lst[0]
    klst.append(k)
    line = []
    for i in range(k):
      line.append((acc, lst[i * 2 + 1], lst[i * 2 + 2]))
      acc += 1
    lines.append(line)

  num = sum(klst)
  edges = [[] for _ in range(num * (m + 1) + 2)]

  for i in range(n - 1):
    line1 = lines[i]
    line2 = lines[i + 1]
    for acc1, x1, d1 in line1:
      for acc2, x2, d2 in line2:
        for j in range(m + 1):
          edges[acc1 + num * j].append((acc2 + num * j, (d1 + d2) * abs(x1 - x2)))
  
  for i in range(n - 2):
    line1 = lines[i]
    line2 = lines[i + 2]
    for acc1, x1, d1 in line1:
      for acc2, x2, d2 in line2:
        for j in range(m):
          edges[acc1 + num * j].append((acc2 + num * (j + 1), (d1 + d2) * abs(x1 - x2)))

  for acc, x, d in lines[0]:
    edges[0].append((acc, 0))
  if m >= 1:
    for acc, x, d in lines[1]:
      edges[0].append((acc + num, 0))
  for acc, x, d in lines[-1]:
    for j in range(m + 1):
      edges[acc + num * j].append((num * (m + 1) + 1, 0))
  for acc, x, d in lines[-2]:
    for j in range(m):
      edges[acc + num * j].append((num * (m + 1) + 1, 0))

  que = []
  heappush(que, (0, 0))
  costs = [INF] * (num * (m + 1) + 2)
  costs[0] = 0
  while que:
    total, node = heappop(que)
    for to, cost in edges[node]:
      if costs[to] > total + cost:
        costs[to] = total + cost
        heappush(que, (total + cost, to))
  print(costs[num * (m + 1) + 1])

Submission status: Time Limit Exceeded

Solution code:
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
def main():
  INF = 10 ** 20
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    lines = []
    acc = 1
    for _ in range(n):
      lst = list(map(int, input().split()))
      k = lst[0]
      line = []
      for i in range(k):
        line.append((acc, lst[i * 2 + 1], lst[i * 2 + 2]))
        acc += 1
      lines.append(line)
  
    num = acc - 1
    edges = [[] for _ in range(num * (m + 1) + 2)]
  
    for i in range(n - 1):
      line1 = lines[i]
      line2 = lines[i + 1]
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          for j in range(m + 1):
            edges[acc1 + num * j].append((acc2 + num * j, (d1 + d2) * abs(x1 - x2)))
    
    for i in range(n - 2):
      line1 = lines[i]
      line2 = lines[i + 2]
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          for j in range(m):
            edges[acc1 + num * j].append((acc2 + num * (j + 1), (d1 + d2) * abs(x1 - x2)))
  
    for acc, x, d in lines[0]:
      edges[0].append((acc, 0))
    if m >= 1:
      for acc, x, d in lines[1]:
        edges[0].append((acc + num, 0))
    for acc, x, d in lines[-1]:
      for j in range(m + 1):
        edges[acc + num * j].append((num * (m + 1) + 1, 0))
    for acc, x, d in lines[-2]:
      for j in range(m):
        edges[acc + num * j].append((num * (m + 1) + 1, 0))
  
    que = []
    heappush(que, (0, 0))
    costs = [INF] * (num * (m + 1) + 2)
    costs[0] = 0
    while que:
      total, node = heappop(que)
      for to, cost in edges[node]:
        new_total = total + cost
        if costs[to] > new_total:
          costs[to] = new_total
          heappush(que, (new_total, to))
    print(costs[num * (m + 1) + 1])
main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    if y > N :
        return 0
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    mem = [[[INF for i in range(200)] for j in range(200)] for k in range(200)]
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    if y > N :
        return 0
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    mem = [[[INF for i in range(150)] for j in range(153)] for k in range(100)]
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    mem = [[[INF for i in range(150)] for j in range(151)] for k in range(75)]
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if y > N :
        return 0
    if mem[m][y][x] != INF:
        return mem[m][y][x]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[m][y][x] = n
    return mem[m][y][x]

while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(N + 4)] for j in range(N + 1)] for k in range(M + 1)]
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))

Submission status: Time Limit Exceeded

Solution code:
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    import sys
    sys.stdout.write(str((dfs(0, 0, M))) + "\n")

Submission status: Time Limit Exceeded

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break

    isi=[[[i,0] for i in xrange(11)]]+[[[float('inf'),float('inf')] for _ in xrange(11)]  for _ in xrange(n)]+[[[i,0] for i in xrange(11)]]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][j+1]=[en[j*2+1],en[j*2+2]]

    dp=[[[float('inf')]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(1,11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            if isi[i+1][j][0]==float('inf'):continue
            for k in xrange(m+1):
                for l in xrange(1,11):
                    if not isi[i][l][0]==float('inf'):
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i][l][0]))
                        if i-1>=0 and k>=1:
                            if isi[i-1][l][0]==float('inf'):continue
                            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))
                    else:
                        if i-1>=0 and k>=1:
                            if isi[i-1][l][0]==float('inf'):continue
                            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))
                            
    ans=float('inf')
    for j in xrange(1,11):
        ans=min(ans,dp[n+1][j][m])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)

def solve(n,m):
    isi=[[[i,0] for i in xrange(11)]]+[[[float('inf'),float('inf')] for _ in xrange(11)]  for _ in xrange(n)]+[[[i,0] for i in xrange(11)]]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][j+1]=[en[j*2+1],en[j*2+2]]

    dp=[[[float('inf')]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(1,11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            if isi[i+1][j][0]==float('inf'):continue
            for k in xrange(m+1):
                for l in xrange(1,11):
                    if not isi[i][l][0]==float('inf'):
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i][l][0]))
                        if i-1>=0 and k>=1:
                            if isi[i-1][l][0]==float('inf'):continue
                            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))
                    else:
                        if i-1>=0 and k>=1:
                            if isi[i-1][l][0]==float('inf'):continue
                            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))

    ans=float('inf')
    for j in xrange(1,11):
        ans=min(ans,dp[n+1][j][m])
    return ans

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    ans=solve(n,m)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)

def solve(n,m):
    isi=[[[i,0] for i in xrange(11)]]+[[[float('inf'),float('inf')] for _ in xrange(11)]  for _ in xrange(n)]+[[[i,0] for i in xrange(11)]]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][j+1]=[en[j*2+1],en[j*2+2]]

    dp=[[[float('inf')]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(1,11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            if isi[i+1][j][0]==float('inf'):continue
            for k in xrange(m+1):
                for l in xrange(1,11):
                    dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i][l][0]))
                    if i-1>=0 and k>=1:
                        if isi[i-1][l][0]==float('inf'):continue
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))

    ans=float('inf')
    for j in xrange(1,11):
        ans=min(ans,dp[n+1][j][m])

    return ans

while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    ans=solve(n,m)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)

def solve(n,m):
    isi=[[[i,0] for i in xrange(11)]]+[[[inf,inf] for _ in xrange(11)]  for _ in xrange(n)]+[[[i,0] for i in xrange(11)]]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][j+1]=[en[j*2+1],en[j*2+2]]

    dp=[[[inf]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(1,11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            if isi[i+1][j][0]==inf:continue
            for k in xrange(m+1):
                for l in xrange(1,11):
                    dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i][l][0]))
                    if i-1>=0 and k>=1:
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))

    ans=float('inf')
    for j in xrange(1,11):
        ans=min(ans,dp[n+1][j][m])

    return ans

inf=10**9
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    ans=solve(n,m)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)

def solve(n,m):
    isi=[[[i,0] for i in xrange(11)]]+[[[inf,inf] for _ in xrange(11)]  for _ in xrange(n)]+[[[i,0] for i in xrange(11)]]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][j+1]=[en[j*2+1],en[j*2+2]]

    dp=[[[inf]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(1,11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            for k in xrange(m+1):
                for l in xrange(1,11):
                    dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i][l][0]))
                    if i-1>=0 and k>=1:
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l][1],isi[i+1][j][1],isi[i+1][j][0]-isi[i-1][l][0]))

    ans=float('inf')
    for j in xrange(1,11):
        ans=min(ans,dp[n+1][j][m])

    return ans

inf=10**9
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    ans=solve(n,m)
    print(ans)

Submission status: Memory Limit Exceeded

Solution code:
from heapq import heappop, heappush

while True:
    n, m = map(int, input().split())
    if not n:
        break

    num_stones = 0
    row_stones = [None] * n
    edges = [None] * n
    for row in range(n):
        (num, *stones) = map(int, input().split())
        row_stones[row] = list(zip(*[iter(stones)] * 2))
        edges[row] = [None] * num

    for row, stones in enumerate(row_stones):
        next_stones = [row_stones[row + j] if row + j < n else [] for j in (1, 2)]
        for i, (column1, slip1) in enumerate(stones):
            edges[row][i] = [{(abs(column1 - column2) * (slip1 + slip2), j)
                              for j, (column2, slip2) in enumerate(next_stones[k])} for k in (0, 1)]

    queue = [(0, m, 0, i) for i in range(len(row_stones[0]))]
    if m:
        queue.extend((0, m - 1, 1, i) for i in range(len(row_stones[1])))

    while queue:
        total_risk, remains, row, i = heappop(queue)
        if row == n - 1 or (remains and row == n - 2):
            print(total_risk)
            break
        next_stones = edges[row][i]
        for risk, j in next_stones[0]:
            heappush(queue, (total_risk + risk, remains, row + 1, j))
        if remains:
            for risk, j in next_stones[1]:
                heappush(queue, (total_risk + risk, remains - 1, row + 2, j))

Submission status: Accepted

Solution code:
"""
nodes
0 ... start
k*num + 1 ~ (k+1)*num ... j=k (k <= m)
num * (m + 1) + 1 ... end
"""
from heapq import heappush, heappop
def main():
  INF = 10 ** 20
  while True:
    n, m = map(int, input().split())
    if n == 0:
      break
    lines = []
    acc = 1
    for _ in range(n):
      lst = list(map(int, input().split()))
      k = lst[0]
      line = [(acc + i, lst[i * 2 + 1], lst[i * 2 + 2]) for i in range(k)]
      acc += k
      lines.append(line)
  
    num = acc - 1
    edges = [[] for _ in range(num * (m + 1) + 2)]
    for line1, line2 in zip(lines, lines[1:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2
          for j in range(m + 1):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
    
    for line1, line2 in zip(lines, lines[2:]):  
      for acc1, x1, d1 in line1:
        for acc2, x2, d2 in line2:
          cost = (d1 + d2) * abs(x1 - x2)
          n1 = acc1
          n2 = acc2 + num
          for j in range(m):
            edges[n1].append((n2, cost))
            n1 += num
            n2 += num
  
    for acc, _, _ in lines[0]:
      edges[0].append((acc, 0))
    if m >= 1:
      for acc, _, _ in lines[1]:
        edges[0].append((acc + num, 0))

    end = num * (m + 1) + 1
    for acc, _, _ in lines[-1]:
      b = acc
      for j in range(m + 1):
        edges[b].append((end, 0))
        b += num
    for acc, _, _ in lines[-2]:
      b = acc
      for j in range(m):
        edges[b].append((end, 0))
        b += num
    
    def search():
      que = []
      heappush(que, (0, 0))
      costs = [INF] * (num * (m + 1) + 2)
      costs[0] = 0
      while que:
        total, node = heappop(que)
        for to, cost in edges[node]:
          new_total = total + cost
          if to == end:
            print(new_total)
            return
          if costs[to] > new_total:
            costs[to] = new_total
            heappush(que, (new_total, to))
    search()
main()

Submission status: Accepted

Solution code:
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, raw_input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

while True:
    n, m = map(int, input().split())
    if not n:
        break

    num_stones = 0
    row_stones = [None] * n
    edges = [None] * n
    visited = [None] * n
    for row in range(n):
        (num, *stones) = map(int, input().split())
        row_stones[row] = list(zip(*[iter(stones)] * 2))
        edges[row] = [None] * num
        visited[row] = [1] * num

    for row, stones in enumerate(row_stones):
        next_stones = [row_stones[row + j] if row + j < n else [] for j in (1, 2)]
        for i, (column1, slip1) in enumerate(stones):
            edges[row][i] = [{(abs(column1 - column2) * (slip1 + slip2), j)
                              for j, (column2, slip2) in enumerate(next_stones[k])} for k in (0, 1)]

    queue = [(0, 0, -m, i) for i in range(len(row_stones[0]))]
    if m:
        queue.extend((0, -1, -m + 1, i) for i in range(len(row_stones[1])))

    while queue:
        total_risk, row, remains, i = heappop(queue)
        row = -row
        if row == n - 1 or (remains and row == n - 2):
            print(total_risk)
            break
        if visited[row][i] <= remains:
            continue
        visited[row][i] = remains
        next_stones = edges[row][i]
        for risk, j in next_stones[0]:
            heappush(queue, (total_risk + risk, -row - 1, remains, j))
        if remains:
            for risk, j in next_stones[1]:
                heappush(queue, (total_risk + risk, -row - 2, remains + 1, j))

Submission status: Accepted

Solution code:
while 1:
    N, M = map(int, input().split())
    if N == M == 0:
        break
    P = []
    K = []
    for i in range(N):
        k, *S = map(int, input().split())
        P.append(list(zip(S[::2], S[1::2])))
        K.append(k)
    INF = 10**18
    memo = {}
    def dfs(i, j, k):
        key = i, j, k
        if key in memo:
            return memo[key]
        if i == N-2 and k < M:
            return 0
        if i == N-1:
            return 0
        res = INF
        xi, di = P[i][j]
        for p in range(K[i+1]):
            xj, dj = P[i+1][p]
            res = min(res, dfs(i+1, p, k) + abs(xi - xj)*(di + dj))
        if i+2 < N and k < M:
            for p in range(K[i+2]):
                xj, dj = P[i+2][p]
                res = min(res, dfs(i+2, p, k+1) + abs(xi - xj)*(di + dj))
        memo[key] = res
        return res
    ans = INF
    for i in range(K[0]):
        ans = min(ans, dfs(0, i, 0))
    if 0 < M:
        for i in range(K[1]):
            ans = min(ans, dfs(1, i, 1))
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    while True:
        n,m=map(int,input().split())
        if n==0:
            break
        kis=[list(map(int,input().split())) for _ in [0]*n]
        dp1=[dict() for _ in [0]*(m+1)]
        dp2=[dict() for _ in [0]*(m+1)]
        dp3=[dict() for _ in [0]*(m+1)]
    
        nows=[dict() for _ in [0]*n]
        for i in range(n):
            j=kis[i][0]
            for k in range(j):
                nows[i][kis[i][2*k+1]]=kis[i][2*k+2]
        for i in range(kis[0][0]):
            dp1[0][kis[0][2*i+1]]=0
        if m>=1:
            for i in range(kis[1][0]):
                dp2[1][kis[1][2*i+1]]=0
        #ここからDP開始
        for k in range(n-1):#行をn-1回分繰り返す
            for l in range(m+1):#飛び越えた回数分
                for i,j in dp1[l].items():#iは現在位置、jはそれまでの最小危険度
                    for x,y in nows[k+1].items():#xは移動先、yは移動先の滑りやすさ
                        plus=j+(nows[k][i]+y)*abs(i-x)
                        if x in dp2[l].keys():
                            dp2[l][x]=min(dp2[l][x],plus)
                        else:
                            dp2[l][x]=plus
            if k==n-2:
                continue
            for l in range(m):#飛び越えた回数-1分
                for i,j in dp1[l].items():#iは現在位置、jはそれまでの最小危険度
                    for x,y in nows[k+2].items():#xは移動先、yは移動先の滑りやすさ
                        plus=j+(nows[k][i]+y)*abs(i-x)
                        if x in dp3[l+1].keys():
                            dp3[l+1][x]=min(dp3[l+1][x],plus)
                        else:
                            dp3[l+1][x]=plus
            dp1=dp2
            dp2=dp3
            dp3=[dict() for _ in [0]*(m+1)]
        m=10**9
        for i in dp1[:-1]:
            if len(i.values())>0:
                m=min(m,min(i.values()))
        for i in dp2:
            if len(i.values())>0:
                m=min(m,min(i.values()))
        print(m)
    
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
def calc(now,nx,w):
    return (now+nx)*abs(w)
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break

    isi=[[0]*11]+[[float('inf')]*11 for _ in xrange(n)]+[[0]*11]
    for i in xrange(1,n+1):
        en=map(int,raw_input().split())
        num=en[0]
        for j in xrange(num):
            isi[i][en[j*2+1]]=en[j*2+2]

    dp=[[[float('inf')]*(m+1) for _ in xrange(11)] for _ in xrange(n+2)]
    for j in xrange(11):
        dp[0][j][0]=0

    for i in xrange(n+1):
        for j in xrange(1,11):
            for k in xrange(m+1):
                for l in xrange(1,11):
                    dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][l][k]+calc(isi[i][l],isi[i+1][j],j-l))
                    if i-1>=0 and k>=1:
                        dp[i+1][j][k]=min(dp[i+1][j][k],dp[i-1][l][k-1]+calc(isi[i-1][l],isi[i+1][j],j-l))

    ans=float('inf')
    for j in xrange(11):
        ans=min(ans,dp[n+1][j][m])
    print(ans)