第７回日本情報オリンピック 本選 「ぴょんぴょん川渡り」

普通にDPするだけ。
INFがINFになってなくて辛い思いをした。

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;
const int INF = 1000000000;

int k[153];
int d[153][11][2];
int dp[153][11][80];
int n,m;

int main(){
  
  while(1){
  
  scanf("%d%d",&n,&m);
  
  if(n == 0)break;
  memset(k,0,sizeof(k));
  memset(d,0,sizeof(d));
  for(int i = 1;i <= n;i++){
    scanf("%d",&k[i]);
    for(int j = 0;j < k[i];j++){
      scanf("%d%d",&d[i][j][0],&d[i][j][1]);
    }
  }

for(int i = 0;i <= 150;i++){
  for(int j = 0;j <= 10;j++){
    for(int l = 0;l <= 79;l++){
      dp[i][j][l] = INF;
    }
  }
}
  k[0] = 1;
  for(int i = 0;i <= 10;i++){
    dp[0][i][m] = 0;
    dp[1][i][m] = 0;
  }
  
  for(int i = 2;i <= n;i++){
    for(int j = 0;j < k[i];j++){
      for(int l = 0;l <= m;l++){
	int tmp = INF;
	for(int a = 0;a < k[i-1];a++){
	  tmp = min(tmp,dp[i-1][a][l]+(d[i][j][1]+d[i-1][a][1])*abs(d[i][j][0]-d[i-1][a][0]));
	}
	dp[i][j][l] = tmp;
	if(l == m)continue;
	
	for(int a = 0;a < k[i-2];a++){
	  if(i == 2 && l == m-1)tmp = 0;
	  tmp = min(tmp,dp[i-2][a][l+1]+(d[i][j][1]+d[i-2][a][1])*abs(d[i][j][0]-d[i-2][a][0]));
	}
	dp[i][j][l] = tmp;
      }
    }
  }
  int ans = INF;
  for(int i = 0;i < k[n];i++){
    for(int j = 0;j <= m;j++){
      ans = min(ans,dp[n][i][j]);
    }
  }
  for(int i = 0;i < k[n-1];i++){
    for(int j = 1;j <= m;j++){
      ans = min(ans,dp[n-1][i][j]);
    }
  }
  printf("%d\n",ans);
  
  }
  
  return 0;
  
}
||<