題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5433

解題思路：

dp[i][j][k]表示在(x,y)點，毅力為k時的最小體力。由于每個點可能會走多次，所以用bfs往四個方向搜索，不過考慮到最優情況，只有比dp[i][j][k]更小，才把它放進隊列里。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<queue> using namespace std;const int maxn = 55; const int inf = 0x3f3f3f3f; const double eps = 1e-8; struct Node {int x,y,t; //t表示意志double power; //體力Node(){}Node(int _x,int _y,int _t,double _power){x = _x, y = _y, t = _t;power = _power;} }; int n,m,k,map[maxn][maxn]; int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; int sx,sy,ex,ey; double dp[maxn][maxn][maxn];void bfs() {queue<Node> q;dp[sx][sy][k] = 0;q.push(Node(sx,sy,k,dp[sx][sy][k]));while(!q.empty()){Node cur = q.front();q.pop();for(int i = 0; i < 4; i++){int newx = cur.x + dir[i][0];int newy = cur.y + dir[i][1];if(newx < 1 || newx > n || newy < 1 || newy > m || map[newx][newy] == -1) continue;Node next;next.x = newx,next.y = newy;next.t = cur.t - 1;double tmp = abs(map[next.x][next.y] - map[cur.x][cur.y]) / (cur.t * 1.0);if(next.t > 0 && dp[next.x][next.y][next.t] > dp[cur.x][cur.y][cur.t] + tmp){dp[next.x][next.y][next.t] = dp[cur.x][cur.y][cur.t] + tmp;next.power = dp[next.x][next.y][next.t];q.push(next);}}} }int main() {int t;char str[maxn];cin >> t;while(t--){cin >> n >> m >> k;for(int i = 1; i <= n; i++){cin >> str + 1;for(int j = 1; j <= m; j++){if(str[j] == '#') map[i][j] = -1;else map[i][j] = str[j] - '0';}}cin >> sx >> sy >> ex >> ey;if(k <= 0) { printf("No Answer\n"); continue; } for(int i = 0; i <= n; i++)for(int j = 0; j <= m; j++)for(int r = 0; r <= k; r++)dp[i][j][r] = inf;bfs();double MIN = dp[ex][ey][1];for(int i = 1; i <= k; i++)MIN = min(MIN,dp[ex][ey][i]);if(abs(MIN - inf) > eps)printf("%.2lf\n",MIN);else printf("No Answer\n");}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5433(bfs+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。