只有一点转化就是一路上的速度在每一段是有变化的，但是实质上到达每一点的速度是一定的v*2^(1-h),那么也就是边权确定，可以用spfa求解，还有一点就是初始化要大，应为可以-25 <= E <= 25，也就是可能存在2^(50)这种数据。
View Code 1 #include2 #include 3 #include 4 #include 5 using std::queue; 6 #define INF 11258999068426240000 7 #define MAXN 11000 8 #define clup(i,j) ((i)*(c+2)+(j)) 9 struct node 10 { 11 int d,next; 12 double c; 13 }edge[5*MAXN]; 14 int head[2*MAXN],p; 15 bool vis[2*MAXN]; 16 double dist[2*MAXN]; 17 int v,r,c,h; 18 queue q; 19 void add(int a,int b,double c) 20 { 21 edge[p].d=b; 22 edge[p].c=c; 23 edge[p].next=head[a]; 24 head[a]=p++; 25 } 26 void spfa() 27 { 28 vis[clup(1,1)]=true; 29 q.push(clup(1,1)); 30 dist[clup(1,1)]=0; 31 int k; 32 while(!q.empty()) 33 { 34 k=q.front(); 35 q.pop(); 36 vis[k]=false; 37 for(int i=head[k];i!=-1;i=edge[i].next) 38 if(dist[edge[i].d]>dist[k]+edge[i].c) 39 { 40 dist[edge[i].d]=dist[k]+edge[i].c; 41 if(!vis[edge[i].d]) 42 { 43 vis[edge[i].d]=true; 44 q.push(edge[i].d); 45 } 46 } 47 } 48 } 49 int main() 50 { 51 //freopen("test.txt","r",stdin); 52 while(scanf("%d %d %d",&v,&r,&c)==3) 53 { 54 memset(head,-1,sizeof(head)); 55 memset(vis,false,sizeof(vis)); 56 p=0; 57 for(int i=1,a;i<=r;++i) 58 for(int j=1;j<=c;++j) 59 { 60 scanf("%d",&a); 61 if(i==1&&j==1) h=a; 62 add(clup(i,j),clup(i-1,j),pow(2.0,(double)(a-h))/v); 63 add(clup(i,j),clup(i,j-1),pow(2.0,(double)(a-h))/v); 64 add(clup(i,j),clup(i+1,j),pow(2.0,(double)(a-h))/v); 65 add(clup(i,j),clup(i,j+1),pow(2.0,(double)(a-h))/v); 66 } 67 for(int i=0;i<=(r+2)*(c+2);dist[i++]=INF); 68 spfa(); 69 printf("%.2f\n",dist[clup(r,c)]); 70 } 71 return 0; 72 }