#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> >q;

#define INF 9999999999999.9

int r,c;
double t[150][150],v[150][150];
int h[150][150];
int vis[150][150],dx[]={-1,1,0,0},dy[]={0,0,-1,1};

void bfs(int x,int y)
{
	memset(vis,0,sizeof(vis));
	for(int i=0;i<r;i++)
		for(int j=0;j<c;j++)
			t[i][j]=INF;
	t[0][0]=0;
	q.push(make_pair(t[0][0],0));
	while(!q.empty())
	{
		pii u=q.top();q.pop();
		int x=u.second/c,y=u.second%c;
		if(x==r-1&&y==c-1) return;
		if(vis[x][y]) continue;
		vis[x][y]=1;
		for(int d=0;d<4;d++)
		{
			int xx=x+dx[d],yy=y+dy[d];
			if(xx>=0&&xx<r&&yy>=0&&yy<c)
			{	
				if(t[xx][yy]>t[x][y]+1.0/v[x][y])
				{
                    v[xx][yy]=v[x][y]*pow(2.0,(h[x][y]-h[xx][yy])*1.0);	
					t[xx][yy]=t[x][y]+1/v[x][y];
					q.push(make_pair(t[xx][yy],(xx*c+yy)));
				}
			}
		}
	}
}

int main()
{
	while(scanf("%lf%d%d",&v[0][0],&r,&c)!=EOF)
	{
		for(int i=0;i<r;i++)
			for(int j=0;j<c;j++)
				scanf("%d",&h[i][j]);
		bfs(0,0);
		printf("%.2lf\n",t[r-1][c-1]);
	}
	return 0;
}

• Re:WA到吐，求找错。。。 (1293) 2011339960140 2012-07-26 17:06:34