×

# Wrong answer in Tri Graphs SPOJ

 0 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 #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)))) <

 0 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. answered 19 Jan '17, 13:45 161●1●4 accept rate: 20% Thanks mohit. Got AC with only this change (19 Jan '17, 13:55)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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