Wrong answer in Tri Graphs SPOJ

help
dynamic-programming
spoj
wa

#1

While I was attempting the question Tri Graphs on spoj I am constantly getting WA for that. Please help me to find the mistake. My code is as follows

#include<bits/stdc++.h>
#define MAX 100002

using namespace std;

int arr[MAX][4] ;
int dp[MAX][4];
int n;

int solve(int i, int j){
    if(i==n-1 and j != 1){
        return arr*[j] + arr*[1];
    }
    if(i == n-1 and j == 1)
        return  arr*[1];
    if( dp*[j] != -1){
        return dp*[j] ;
    }
    else{
        int ans ;
        ans = arr*[j] ;
        switch(j){
            case 0: ans += min(solve(i+1, j+1), min(solve(i+1, j), solve(i, j+1)));
                    break ;
            case 1: ans += min(solve(i+1, j+1), min(min(solve(i+1, j-1), solve(i+1, j)), solve(i,j+1)));
                    break ;
            case 2: ans += min(solve(i+1, j-1), solve(i+1, j));
                    break ;
        }
        dp*[j] = ans ;
        return ans ;
    }
}
int main(){
    int counter =  0 ;
    while(true){
        counter += 1 ;
        cin >> n ;
        if(n == 0)
            break ;
        memset(dp, -1, sizeof(dp));
        for(int i=0 ; i < n ; i++){
            for(int j=0; j<3;j++){
                cin >> arr*[j] ;
            }
        }
        int i=0, j=1;
        
        cout << counter << ". " << arr[0][1] +  min( solve(i+1, j-1), min(solve(i+1,j), min(solve(i+1,j+1), solve(i, j+1)))) <<endl;
    }
return 0;
}

#2

In each dp*[j], you are storing the shortest path to reach from (i, j) to (n - 1, 1). [0-indexed]


if(i==n-1 and j != 1){
        return arr*[j] + arr*[1];
}

This base case assumes that state (n - 1, 1) is reachable from state (n - 1, 2) while this is not true for the graph structure as mentioned in the problem.


#3

Thanks mohit. Got AC with only this change