You are not logged in. Please login at www.codechef.com to post your questions!

×

Wrong answer in Tri Graphs SPOJ

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[i][j] + arr[i][1];
    }
    if(i == n-1 and j == 1)
        return  arr[i][1];
    if( dp[i][j] != -1){
        return dp[i][j] ;
    }
    else{
        int ans ;
        ans = arr[i][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[i][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[i][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;
}

asked 19 Jan '17, 11:59

nickzuck_007's gravatar image

3★nickzuck_007
191621
accept rate: 14%


In each dp[i][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[i][j] + arr[i][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.

link

answered 19 Jan '17, 13:45

mohit22995's gravatar image

5★mohit22995
16114
accept rate: 20%

Thanks mohit. Got AC with only this change

(19 Jan '17, 13:55) nickzuck_0073★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,718
×2,172
×1,136
×1,070

question asked: 19 Jan '17, 11:59

question was seen: 395 times

last updated: 19 Jan '17, 13:55