hdu a strang lift

本文主要是介绍hdu a strang lift，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

按得最短路做的，DP 搜索也能搞

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAX_N 10000
#define INF 0xffff
typedef pair<int, int> P;int n,v,u;
int G[MAX_N][MAX_N];
int d[MAX_N];
bool used[MAX_N];
int a[MAX_N];void dijkstra(int v){for(int i = 1;i <= n; i++){d[i] = G[v][i];}fill(used, used + n, false);d[v] = 0;used[v] = 1;for(int i = 2; i <= n; i++){int flag = v,min = INF;for(int u = 1;u < n; u++){ if(!used[u] && d[u] < min){flag = u;min = d[u];}}used[flag] = 1;for(int j = 1; j <=n;j++){if(!used[j] && G[flag][j] < INF){int newd = d[flag] + G[flag][j];if(newd < d[j])d[j] = newd;}}}
}
int main(){while(scanf("%d", &n) && n){scanf("%d%d",&v, &u);for(int i = 1;i <= n; i++)for(int j = 1;j <= n; j++)G[i][j] = INF;for(int i = 1;i <= n; i++){scanf("%d", &a[i]);G[i][i + a[i]] = 1;if(i >= a[i] + 1){G[i][i - a[i]] = 1;}}dijkstra(v);if(d[u] >= INF)printf("-1\n");else printf("%d\n", d[u]);}return 0;
}

这篇关于hdu a strang lift的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---