SPOJ : ACPC 10D Trigraphs Solution

This problem could be solved by using DP.
Step 1:
        Initialse the adjacent nodes to the source node.
Step 2:
        Loop Across the other i nodes from 2 to N and initialise them.

P re-Requesite: DP
     However Learning Floyd Warshall Algorithm would help you in solving this problem.



Code:


#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

int main()
{
int i=1;
while(1) {
int n;
cin >>n;
if(n==0)
return 0;
int a[n][3];
for (int i=0;i<n;i++)
cin >>a[i][0]>>a[i][1]>>a[i][2];
cout<<i<<". ";
if(n==1)
cout<<a[0][1]<<endl;
else {
                                                               // Initialisation Step
a[1][0] += a[0][1];
a[0][2] += a[0][1];
a[1][1] += min(min(a[1][0],a[0][1]),a[0][2]);
a[1][2] += min(min(a[0][2],a[0][1]),a[1][1]);


                                                                 // Calculating the remaing nodes
for(int i  = 2 ; i<n;i++)
{
a[i][0] += min(a[i-1][0],a[i-1][1]);
a[i][1] += min(min(min(a[i][0],a[i-1][0]),a[i-1][1]),a[i-1][2]);
a[i][2] += min(min(a[i][1],a[i-1][1]),a[i-1][2]);
}
cout <<a[n-1][1]<<endl;
i++;
}
}
return 0;
}