最短路
题意：比较懒有点难描述，所以不说了，看Hint可以看懂的
本题的巧妙之处是其实无论怎么走，从起点（固定的）走到任何一个点，到达那个点的时候速度都是确定的
因为 速度为spa ，a--->b---->c ， b点速度为 spb = spa * 2^(ha-hb) , c点速度为 spc = spb * 2^(hb - hc)
式子一合并，就是 spc = spa * 2^(ha - hc) ，可见从点a走到点c，无论中间经过什么点，最后计算速度，之和点a和点c的高度差有关，当然和点a的速度也有关
而起点是固定的（1,1），而起始速度是知道的，那么从点（1,1）走到任何一个点时的速度也就是唯一确定的了
而根据题意，从点u走向点v，花费的时间其实只是由点u当时的速度决定的，和点v没有关系，所以其实从点u走向任何一个相邻的点，时间都是唯一确定的，因为点u的速度是唯一确定的
这样从一个点转移到另一个点的时间唯一确定了，那么就可以最短路了
代码中使用spfa
#include <cstdio> #include <cstring> #include <cmath> #include <utility> #include <queue> #include <vector> using namespace std; const int N = 110; const double INF = 10000000000; const int dx[4] = {-1,1,0,0}; const int dy[4] = {0,0,-1,1}; int row , col; double initsp; double sp[N][N]; double d[N][N]; bool inq[N][N]; int h[N][N]; struct node { int x,y; }; typedef struct node node; void spfa() { queue<node>q; node temp; for(int i=1; i<=row; i++) for(int j=1; j<=col; j++) { d[i][j] = INF; inq[i][j] = false; } while(!q.empty()) q.pop(); temp.x = 1; temp.y = 1; d[1][1] = 0; inq[1][1] = true; q.push(temp); while(!q.empty()) { int x1,y1,x2,y2; temp = q.front(); q.pop(); x1 = temp.x; y1 = temp.y; inq[x1][y1] = false; for(int k=0; k<4; k++) { x2 = x1 + dx[k]; y2 = y1 + dy[k]; if(x2 < 1 || x2 > row || y2 < 1 || y2 > col) continue; double w = 1./(sp[x1][y1]); if(d[x1][y1] + w < d[x2][y2]) { d[x2][y2] = d[x1][y1] + w; if(!inq[x2][y2]) { inq[x2][y2] = true; temp.x = x2; temp.y = y2; q.push(temp); } } } } printf("%.2f\n",d[row][col]); } int main() { scanf("%lf%d%d",&initsp,&row,&col); for(int i=1; i<=row; i++) for(int j=1; j<=col; j++) { scanf("%d",&h[i][j]); sp[i][j] = initsp * pow(2.0 , h[1][1]-h[i][j]); } sp[1][1] = initsp; spfa(); return 0; }