题意：
Bessie在一个row*col的矩形区域内滑雪，起点为左上角，已知初始速度v，从a 点到 b 点时，速度变为v(a)*2^(A-B)(A,B为对应点的高度),从 a 到 b 所需的时间为 a 的速度的倒数，她可向前后左右四个方向移动，求其到右下角的最少时间。
分析：
每点的速度是固定的：例如从a->b->c;则c出发的速度就是V*2^(A-B）*2^(B-C)=V*2^(A-C);时间则是速度的倒数。
注意：
1、inf要足够大
2、因为矩阵内的值范围[-25,25],如果用1<<x的方式求2的幂，很显然这个数会整数超出范围。所以要用 __int64 t=1;
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #include <queue> 7 8 using namespace std; 9 10 #define inf 99999999999LL 11 int dx[]={0,0,-1,1}; 12 int dy[]={-1,1,0,0}; 13 14 struct point 15 { 16 int x; 17 int y; 18 }; 19 20 double dis[103][103]; 21 int map[103][103]; 22 bool vis[103][103]; 23 int V,R,C; 24 25 26 bool isok(point po) 27 { 28 if(po.x>0 && po.x<=R && po.y>0 && po.y<=C) 29 return true; 30 return false; 31 } 32 33 void spfa(int r,int c,int v) 34 { 35 queue <point> Q; 36 __int64 t=1; 37 double k; 38 dis[1][1]=0; 39 point p={1,1}; 40 Q.push(p); 41 vis[1][1]=1; 42 while(!Q.empty()) 43 { 44 p=Q.front(); 45 Q.pop(); 46 vis[p.x][p.y]=0; 47 int s=map[1][1]-map[p.x][p.y]; 48 if(s>=0) 49 k=(t<<s)*v; 50 else 51 k=1.0/(t<<(-s))*v; 52 for(int i=0;i<4;i++) 53 { 54 point next; 55 next.x=p.x+dx[i]; 56 next.y=p.y+dy[i]; 57 if(isok(next)) 58 { 59 if(dis[next.x][next.y] > dis[p.x][p.y] + 1.0/k) 60 { 61 dis[next.x][next.y] = dis[p.x][p.y] + 1.0/k; 62 if(!vis[next.x][next.y]) 63 { 64 vis[next.x][next.y]=1; 65 Q.push(next); 66 } 67 } 68 } 69 } 70 } 71 } 72 73 int main() 74 { 75 while(scanf("%d%d%d",&V,&R,&C) != EOF) 76 { 77 memset(vis,0,sizeof(vis)); 78 for(int i=1;i<=R;i++) 79 for(int j=1;j<=C;j++) 80 { 81 scanf("%d",&map[i][j]); 82 dis[i][j]=inf; 83 } 84 spfa(R,C,V); 85 printf("%.2f\n",dis[R][C]); 86 87 } 88 return 0; 89 }