速度在原点是恒定的，所以每个点的速度也能直接算出来，然后最短时间是就最短路。
迪杰斯特拉的时候 INF要开足够大，要不然会wa
#include<cstdio> #include<cmath> #include<cstring> #include<queue> #include<algorithm> #include<iostream> using namespace std; const int maxn = 105; const double inf = (1<<20)*1.0; int cc[maxn][maxn]; double V[maxn][maxn]; double dist[maxn][maxn]; int dir[4][2] = {1,0,-1,0,0,1,0,-1}; struct Edge { int x,y; double w; Edge(int a,int c,double b):x(a),y(c),w(b){} bool operator < (const Edge& T)const{ return w>T.w; } }; void dij(int r,int c) { priority_queue<Edge>q; for(int i=0;i<=r;i++) for(int j=0;j<=c;j++) dist[i][j] = inf; q.push(Edge(0,0,0)); dist[0][0] = 0; while(!q.empty()) { Edge fr = q.top(); q.pop(); int x = fr.x; int y = fr.y; for(int i=0;i<4;i++) { int nx = x + dir[i][0]; int ny = y + dir[i][1]; if(nx<0||nx>=r||ny<0||ny>=c) continue; double w = 1.0/V[x][y]; if(dist[nx][ny]>dist[x][y] + w) { dist[nx][ny] = dist[x][y] + w; q.push(Edge(nx,ny,dist[nx][ny])); } } } printf("%.2f\n",dist[r-1][c-1]); } int main() { int r,c; double v; cin>>v>>r>>c; for(int i=0;i<r;i++) { for(int j=0;j<c;j++) { scanf("%d",&cc[i][j]); V[i][j] = v*pow(2,(cc[0][0]-cc[i][j])); } } //V[0][0] = v; dij(r,c); return 0; }