2982.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2982  User Id:fzk 
Memory:76K  Time:156MS
Language:C++  Result:Accepted

Source 

#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( "%d\n", cast[n][m] );
	}
	return 0;
}