点击打开链接hdu 1548
思路:最短路+Dijkstra
分析:数据量不大直接Dijkstra即可,但是注意要把图处理成有向图,因为题目中的电梯是有分上下两个分向的。
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 210
#define INF 0xFFFFFFF
int n , A , B;
int value[MAXN][MAXN];
int dis[MAXN];
int vis[MAXN];
void Dijkstra(int s){
int pos;
memset(vis , 0 , sizeof(vis));
for(int i = 1 ; i <= n ; i++)
dis[i] = INF;
dis[s] = 0;
for(int i = 1 ; i <= n ; i++){
pos = -1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && (pos == -1 || dis[j] < dis[pos]))
pos = j;
}
vis[pos] = 1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && dis[j] > dis[pos] + value[pos][j])
dis[j] = dis[pos] + value[pos][j];
}
}
}
int main(){
int k;
while(scanf("%d" , &n) &&n){
scanf("%d%d" , &A , &B);
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++)
value[i][j] = INF;
}
for(int i = 1 ; i <= n ; i++){
scanf("%d" , &k);
/*处理成有向图*/
if(i-k >= 1)
value[i][i-k] = 1;
if(i+k <= n)
value[i][i+k] = 1;
}
Dijkstra(A);
if(dis[B] != INF)
printf("%d\n" , dis[B]);
else
printf("-1\n");
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu_2102_passed_sorce
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类