本文主要是介绍uva 10269 - Adventure of Super Mario（Floyd + Dijkstra + dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 10269 - Adventure of Super Mario
题目大意：马里奥就出桃子之后，要返回自己所居住的村子标号为1，给出A 和 B表示有A个村子和B个城堡，大魔王所居住的城堡A + B，1 ~A为村子，A + 1 ~ B为城堡。现在有m条路，连接着村子、城堡；每条路有它的距离；然后马里奥可以使用k次魔法，可以从一个地方瞬间移动到另外一个地方（不可以在路中间停，并且距离不超过l）；并且使用魔法的时候不能穿过城堡。问说玛丽奥最少花费的时间。
解题思路：因为马里奥会使用魔法，所以要用Floyd算法求出任意两个点的最短距离（用来判断说是否可以使用魔法，中间不能经过城堡），然后dp[i][j]表示移动i使用j次魔法的最短时间，然后就是Dijkstra算法。
#include <stdio.h>
#include <string.h>#define min(a,b) (a)<(b)?(a):(b)const int N = 105;
const int K = 15;
const int INF = 0x3f3f3f3f;int A, B, n, m, l, k;
int dp[N][K], g[N][N], f[N][N], vis[N][K];void init() {scanf("%d%d%d%d%d", &A, &B, &m, &l, &k);n = A + B;memset(g, INF, sizeof(g));memset(f, INF, sizeof(f));memset(vis, 0, sizeof(vis));int a, b, c;for (int i = 0; i < m; i++) {scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = f[a][b] = f[b][a] = c;}for (int i = 1; i <= n; i++)f[i][i] = 0;
}void Floyd() {for (int t = 1; t <= A; t++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)f[i][j] = min(f[i][j], f[i][t] + f[t][j]);
}void solve() {memset(dp, INF, sizeof(dp));dp[n][0] = 0;m = n * (k + 1);int u, v, c;for (int t = 0; t < m; t++) {c = INF;for (int i = 1; i <= n; i++) {for (int j = 0; j <= k; j++) {if (!vis[i][j] && dp[i][j] < c) {u = i, v = j;c = dp[i][j];}}}vis[u][v] = 1;for (int i = 1; i <= n; i++) {if (f[u][i] <= l && dp[i][v + 1] > dp[u][v]) {dp[i][v + 1] = dp[u][v];vis[i][v + 1] = 0;}if (dp[i][v] > dp[u][v] + g[u][i]) {dp[i][v] = dp[u][v] + g[u][i];vis[i][v] = 0;}}}printf("%d\n", dp[1][k]);
}int main () {int cas;scanf("%d", &cas);while (cas--) {init();Floyd();solve();}return 0;
}
这篇关于uva 10269 - Adventure of Super Mario（Floyd + Dijkstra + dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
