#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#define inf 9999999999999.0

using namespace std;

int v,c,r;
double h[105][105];
int num;
struct node
{
	int v;
	double dis;
};
vector<node>map[40005];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

bool judge(int x,int y)
{
	if(x>=1&&x<=r&&y>=1&&y<=c)
		return true;
	else
		return false;
}

void spfa(int s,double dis[])
{
	int i;
	bool used[10005];
	memset(used,0,sizeof(used));
	used[s]=1;
	for(i=0;i<10005;i++)
		dis[i]=inf;
	dis[s]=0;
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		used[u]=0;
		for(i=0;i<map[u].size();i++)
		{
			node p=map[u][i];
			if(dis[p.v]>dis[u]+p.dis)
			{
				dis[p.v]=dis[u]+p.dis;
				if(!used[p.v])
				{
					used[p.v]=1;
					q.push(p.v);
				}
			}
		}
	}
}

double get_ans()
{
	double dis[10005];
	spfa(1,dis);
	return dis[c*r];
}

int main()
{
	int i,j,k;
	num=0;
	scanf("%d%d%d",&v,&r,&c);
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
			scanf("%lf",&h[i][j]);
	int nx;
	int ny;
	for(i=1;i<=r;i++)
		for(j=1;j<=c;j++)
		{
			node p;
			p.dis=1.0/(v*pow(2.0,(h[1][1]-h[i][j])));
			for(k=0;k<4;k++)
			{	
				nx=i+dx[k];
				ny=j+dy[k];
				if(judge(nx,ny))
				{
					p.v=(nx-1)*c+ny;
					map[(i-1)*c+j].push_back(p);
				}
			}
		}
	double ans;
	ans=get_ans();
	printf("%.2lf\n",ans);
	return 0;
}

• 我的spfa开始也超时，是因为我用位移的时候1<<delta越界了，出现了负环。但是你这里用pow函数，不知是不是也出现了负环。 (0) 2008022118 2010-10-02 12:04:20