POJ3037 Skiing

Skiing

题目大意：

给定一个M*N的网格，已知在每个网格中的点可以向上下左右四个方向移动一个单位，每个点都有一个高度值。 从每个点开始移动时存在一个速度值，从A点移动到B点，则此时B点的速度为"A的速度*2^(A的高度值－B的高度值)"，而A点移动到B点所用的时间则是A点开始移动的速度值的倒数。 提供网格的长和宽，每个点的高度，以及在左上角的点的出发速度，问从左上角的点到右下角的点最少需要多少时间。

大致思路：

这道题，我们可以注意到其实在某一个点的速度是个固定值，因为不管怎么到达该点，这个点的速度都是1/(v*(2^(起点与该点的深度差)))，求出每个点的速度后，再求最短路径就好了。

代码：

 #include<queue>

 #include<cmath>

 #include<cstdio>

 #define Max_double 11258999068426240000;

 #define N 110

 using namespace std;

 int d[][]={{,-},{,},{,},{-,}};

 struct hehe{

     int x;

     int y;

 };

 hehe p,qqq;

 queue<hehe>q;

 double dis[N][N];

 bool exist[N][N];

 int deep[N][N],v,n,m;

 double spfa(){

     p.x=;

     p.y=;

     dis[][]=;

     exist[][]=;

     q.push(p);

     while(!q.empty()){

         p=q.front();

         q.pop();

         exist[p.x][p.y]=;

         double k=1.0/(v*pow(,1.0*deep[][]-deep[p.x][p.y]));

         for(int i=;i<;i++){

             int x1=p.x+d[i][],y1=p.y+d[i][];

             if(x1>=&&x1<=n&&y1>=&&y1<=m){

                 if(dis[x1][y1]>dis[p.x][p.y]+k){

                     dis[x1][y1]=dis[p.x][p.y]+k;

                     if(!exist[x1][y1]){

                         qqq.x=x1;

                         qqq.y=y1;

                         q.push(qqq);

                         exist[qqq.x][qqq.y]=;

                     }

                 }

             }

         }

     }

     return dis[n][m];

 }

 int main(){

     scanf("%d%d%d",&v,&n,&m);

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++){

             scanf("%d",&deep[i][j]);

             dis[i][j]=Max_double;

         }

     printf("%.2lf",spfa());

     return ;

 }