3037.txt

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

Problem Id:3037  User Id:fzk 
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1,-1, 0,  0 };
struct node {
	int i, j, k;
	double time;
};
struct cmp {
	bool operator()( node a, node b ) const {
		return a.time > b.time;
	}
};
priority_queue< node, vector<node>, cmp > q;
double ans[100][100][101];
int h[100][100];
int main() {
	int n, m, i, j, k, v;
	node nd, ndt;
	double temp;
	scanf( "%d%d%d", &v, &n, &m );	
	for( i=0; i<n; i++ )
	for( j=0; j<m; j++ ) {
		scanf( "%d", &h[i][j] );
		for( k=0; k<100; k++ )
			ans[i][j][k] = 1e100;
	}
	ans[0][0][50] = 0;
	nd.i = 0, nd.j = 0, nd.k = 50, nd.time = 0;
	q.push( nd );
	while( 1 ) {
		nd = q.top();
		q.pop();
		if( nd.i == n-1 && nd.j == m-1 )
			break;
		for( i=0; i<4; i++ ) {
			ndt = nd;
			ndt.i+=dx[i];
			ndt.j+=dy[i];			
			if( ndt.i >= 0 && ndt.i < n && ndt.j >= 0 && ndt.j < m ) {
				ndt.k+=h[nd.i][nd.j]-h[ndt.i][ndt.j];
				if( ans[ndt.i][ndt.j][ndt.k] > ( temp = ans[nd.i][nd.j][nd.k]+1/pow(2,nd.k-50) ) ) {
					ans[ndt.i][ndt.j][ndt.k] = temp;
					ndt.time = temp; 
					q.push( ndt );
				}
			}
		}
	}
	printf( "%.2lf\n", nd.time/v );
	return 0;
}