読者です 読者をやめる 読者になる 読者になる

AOJ Problem 0530 : Pyon-Pyon River Crossing

404 Not Found

謎のWAると心が折れそうになる。1行目の石が0の時を考慮していなかった。こういう見落としパチモンの時もあったけどデバグに時間掛かりすぎてヤバイ。

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n , m;
	
	while(cin >> n >> m , n ){
		int pos[151][10] ={0};
		int rate[151][10] = {0};
		int cnt[151] = {0};
		for(int i = 1 ; i <= n ;i++){
			int k; cin >> k;
			cnt[i] = k;
			rep(j,k){
				cin >> pos[i][j] >> rate[i][j];
			}
		}
		n++;
		
		int dp[152][10][80] = {0};
		rep(i,151)rep(j,10)rep(k,80)dp[i][j][k] = (1<<29);
		rep(j,10)rep(k,80)dp[0][j][k] = 0;
		rep(j,10)rate[0][j] = 0;
		cnt[0] = 1;
		
		for(int k = m ; k>=0 ; k--){
			for(int i = 1;i<n;i++){
				rep(prev,cnt[i-1]){
					rep(cur,cnt[i]){
						if(i-1){
							dp[i][cur][k] = min(
								dp[i][cur][k], 
								dp[i-1][prev][k] + (rate[i][cur]+rate[i-1][prev]) * abs( pos[i][cur] - pos[i-1][prev] )
							);
						}else{
							dp[i][cur][k] = 0;
						}
					}
				}
			}

			if(k){
				for(int i=2;i<n;i++){
					rep(prev,cnt[i-2]){
						rep(cur,cnt[i]){
							if(i-2){
								dp[i][cur][k-1] = min(
									dp[i][cur][k-1] , 
									dp[i-2][prev][k] + (rate[i][cur]+rate[i-2][prev]) * abs( pos[i][cur] - pos[i-2][prev] )
								);
							}else{
								dp[i][cur][k-1] = 0;
							}
						}
					}
				}
			}
		}
		
		int ret = (1<<29);
		rep(k,m+1){
			if(k)rep(i,cnt[n-2])ret = min(ret,dp[n-2][i][k]);
			rep(i,cnt[n-1])ret = min(ret,dp[n-1][i][k]);
		}
		cout << ret << endl;
		break;
	}
}