poj 3037 -- Skiing spfa

53 阅读 0 评论 35 点赞

我是靠谱客的博主活力百褶裙，最近开发中收集的这篇文章主要介绍poj 3037 -- Skiing spfa，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

poj 3037 -- Skiing spfa

Bessie and the rest of Farmer John's cows are taking a trip this winter to go skiing. One day Bessie finds herself at the top left corner of an R (1 <= R <= 100) by C (1 <= C <= 100) grid of elevations E (-25 <= E <= 25). In order to join FJ and the other cows at a discow party, she must get down to the bottom right corner as quickly as she can by travelling only north, south, east, and west.

Bessie starts out travelling at a initial speed V (1 <= V <= 1,000,000). She has discovered a remarkable relationship between her speed and her elevation change. When Bessie moves from a location of height A to an adjacent location of eight B, her speed is multiplied by the number 2^(A-B). The time it takes Bessie to travel from a location to an adjacent location is the reciprocal of her speed when she is at the first location.

Input

* Line 1: Three space-separated integers: V, R, and C, which respectively represent Bessie's initial velocity and the number of rows and columns in the grid.

* Lines 2..R+1: C integers representing the elevation E of the corresponding location on the grid.

Output

A single number value, printed to two exactly decimal places: the minimum amount of time that Bessie can take to reach the bottom right corner of the grid.

Sample Input

1 3 3
1 5 3
6 3 5
2 4 3

Sample Output

29.00

Hint

Bessie's best route is:
Start at 1,1 time 0 speed 1
East to 1,2 time 1 speed 1/16
South to 2,2 time 17 speed 1/4
South to 3,2 time 21 speed 1/8
East to 3,3 time 29 speed 1/4

题意是一头牛从左上角走到右下角，给你左上角的初始速度，每走一点，速度乘以2的两点的高度差次方，时间是速度的反比，问最短时间

这道题实在最短路的专题下挂出来的，可以看出从u到v的时间是由u的速度决定的，因为初始速度是固定的，而速度的的改变只和高度差有关，这样每一个点的速度都是固定的（这道题的关键），那么每一点到上下左右的时间都是确定得了，这就构成了图。

接下来就是如何找最短路了，这是我第一次用spfa算法写，spfa算法就是首先把源点加入队列里，然后对其相邻的边进行松弛，如果松弛成功，且这个点不在队列里，就把他加入队列里，写这个题的时候感觉和广搜十分相似，似乎这两个算法是同一个人写出来的，但有些地方还是不一样的，spfa里一个点可以多次加入队列，广搜只有一次

#include<stdio.h>
#include<queue>
#include<math.h>
using namespace std;
const double INF=10000000000;
const int maxn=110;
double v[maxn][maxn];
double d[maxn][maxn];
int h[maxn][maxn];
bool vis[maxn][maxn];
int R,C;
double V;
struct node{
	int x;
	int y;
};
int next1[4][2]={
  {0,1},{1,0},{-1,0},{0,-1}
};
void spfa()
{
	queue<node> q;
	struct node temp1,temp2;
	
	for(int i=1;i<=R;i++)
	   for(int j=1;j<=C;j++)
	   {
	   	   d[i][j]=INF;
		   vis[i][j]=false;   
	   }
	temp1.x=1;temp1.y=1;
	q.push(temp1);
	vis[1][1]=true;
	d[1][1]=0;
	
	while(!q.empty())
	{
		temp1=q.front();
		q.pop();
		vis[temp1.x][temp1.y]=false;
		
		for(int i=0;i<=3;i++)
		{
			temp2=temp1;
			temp2.x+=next1[i][0];
			temp2.y+=next1[i][1];
			
			if(temp2.x<1||temp2.y<1||temp2.x>R||temp2.y>C)
			   continue;
			
			double w=(1.0)/v[temp1.x][temp1.y];
			if(d[temp1.x][temp1.y]+w<d[temp2.x][temp2.y])
			{
				d[temp2.x][temp2.y]=d[temp1.x][temp1.y]+w;
				if(!vis[temp2.x][temp2.y])
				{
				    q.push(temp2);
					vis[temp2.x][temp2.y]=true;
				}
			}   
		}
	}  
	printf("%.2fn",d[R][C]); 
}
int main(void)
{
	scanf("%lf%d%d",&V,&R,&C);
	for(int i=1;i<=R;i++)
	    for(int j=1;j<=C;j++)
	    {
	    	scanf("%d",&h[i][j]);
	    	v[i][j]=V*pow(2.0,double(h[1][1])-double(h[i][j]));
	    }
	v[1][1]=V;    
    spfa();
    return 0;
}