题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1548
题意:
有一个特别的电梯,第i层有一个对应的数字ki, 对于第i层按上升键up可升上到i+k[i]层,按下降键down到达i-k[i]层,到达的楼层最高不能超过n层,最低不能小于1层。给你一个起点A和终点B,问最少要按几次上升键或者下降键到达目的地,不可达则输出-1。
分析:
可以这构造成边权值为1的有向图,问题就可以变成求起点到终点的最短路径问题。
可以用 最短路径算法 or BFS
code1: (BFS)
Accepted | 1548 | 0MS | 228K | 1109 B | G++ |
#include <cstdio> #include <cstring> #include <queue> #define N 205 using namespace std; bool used[N]; int a[N]; int n, s, e; int flag, ans; struct node { int x, step; }; void bfs() { node first, next; queue<node> q; first.x = s,first.step = 0; q.push(first); used[s] = true; while(!q.empty()) { first = q.front(), q.pop(); if(first.x==e) { flag = 1; ans = first.step; return ; } next.step = first.step + 1; next.x = first.x - a[first.x]; if(next.x>0&&!used[next.x]) used[next.x] = true, q.push(next); next.x = first.x + a[first.x]; if(next.x<=n&&!used[next.x]) used[next.x] = true, q.push(next); } } int main() { int i; while(~scanf("%d",&n),n) { scanf("%d%d",&s,&e); for(i=1; i<=n; i++) scanf("%d",a+i); ans = 0; flag = 0; memset(used,false,sizeof(used)); bfs(); if(flag) printf("%d\n",ans); else printf("-1\n"); } return 0; }
code2:(Dijkstra)
Accepted | 1548 | 31MS | 368K | 1207 B | C |
#include <stdio.h> #include <string.h> #define N 205 #define INF 0x7f7f7f7f int map[N][N], d[N]; int vis[N]; int n, s, e; int Dijkstra() { int i, j, min, k; for(i=1; i<=n; i++) { d[i] = map[s][i]; vis[i] = 0; } vis[s] = 1; d[s] = 0; for(i=1; i<n; i++) { min =INF; for(j=1; j<=n; j++) if(!vis[j] && d[j]<min) min=d[k=j]; if(min==INF) break; vis[k] = 1; if(vis[e]) break; for(j=1; j<=n; j++) if(!vis[j]&d[j]>d[k]+map[k][j]) d[j] = d[k]+map[k][j]; } if(!vis[e]||d[e]==INF) return -1; else return d[e]; } int main() { int c, i, j; while(scanf("%d",&n),n) { scanf("%d%d",&s,&e); memset(map,INF,sizeof(map)); for(i=1; i<=n; i++) { scanf("%d",&c); if(c==0) continue; if(i-c>0) map[i][i-c] = 1; if(i+c<=n) map[i][i+c] = 1; } if(s==e) printf("0\n"); else if(s<1||e<1||s>n||e>n) printf("-1\n"); else { printf("%d\n", Dijkstra() ); } } return 0; }