Poj Solution 2982

http://poj.org/problem?id=2982

#include "stdio.h"
#include "memory.h"


int cast[111][111];
int a[111], b[111], c[111];
int n, m, k;
bool sign[111];

int main() {
    int i, j, l, s, x, y, h;
    while( 1 ) {
        scanf( "%d%d%d", &n, &m, &k );
        if( !n && !m && !k )
            break;

        for( i=0; i<k; i++ ) {
            scanf( "%d%d%d", a+i, b+i, c+i );
        }
        
            
        for( i=0; i<=n; i++ )
        for( j=0; j<=m; j++ )
            cast[i][j] = 99999999;
        
        cast[0][0] = 0;
        
        for( i=0; i<=n; i++ ) {
            memset( sign, 0, sizeof sign );
            for( j=0; j<=m; j++ ) {
                
                h = -1;
                for( l=0; l<=m; l++ )
                    if( !sign[l] && ( h < 0 || cast[i][h] > cast[i][l] ) )
                        h = l;
                sign[h] = true;
                
                if( cast[i][h] == 99999999 )
                    break;
                    
                s = cast[i][h];
                for( l=0; l<k; l++ ) {
                    x = i+a[l];
                    y = h+b[l];
                    if( 0 <= x && x <= n && 0 <= y && y <= m && s+c[l] < cast[x][y] )
                        cast[x][y] = s+c[l];
                }
            }
        }
        if( cast[n][m] == 99999999 )
            cast[n][m] = -1;
        printf( "%dn", cast[n][m] );
    }
    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *