首页 > 代码库 > HDU 1548 A strange lift （Dijkstra）
HDU 1548 A strange lift （Dijkstra）
https://vjudge.net/problem/HDU-1548
题意：
电梯每层有一个不同的数字，例如第n层有个数字k，那么这一层只能上k层或下k层，但是不能低于一层或高于n层，给定起点与终点，要求出最少要按几次键。
思路：
可以用BFS，也可以用迪杰斯特拉算法。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 using namespace std; 6 7 #define INF 100000000 8 9 int n, A, B;10 int map[205][205];11 int vis[205];12 int d[205];13 int num[205];14 15 void Dijkstra()16 {17 memset(vis, 0, sizeof(vis));18 for (int i = 1; i <= n; i++)19 {20 num[i] = map[A][i];21 }22 num[A] = 0;23 vis[A] = 1;24 for (int i = 1; i < n; i++)25 {26 int min = INF;27 int pos;28 for (int j = 1; j <= n; j++)29 {30 if (num[j] < min && !vis[j])31 {32 pos = j;33 min = num[j];34 }35 }36 if (min == INF) break;37 vis[pos] = 1;38 for (int j = 1; j <= n; j++)39 {40 if (num[pos] + map[pos][j] < num[j] && !vis[j])41 num[j] = num[pos] + map[pos][j];42 }43 }44 if (num[B] == INF) printf("-1\n");45 else printf("%d\n", num[B]);46 }47 48 int main()49 {50 //freopen("D:\\txt.txt", "r", stdin);51 int a;52 while (scanf("%d", &n) && n)53 {54 scanf("%d%d", &A, &B);55 for (int i = 1; i <= n; i++)56 for (int j = 1; j <= n; j++)57 map[i][j] = INF;58 for (int i = 1; i <= n; i++)59 {60 scanf("%d", &a);61 if (i + a <= n)62 map[i][i + a] = 1;63 if (i - a >= 0)64 map[i][i - a] = 1; 65 }66 Dijkstra();67 }68 return 0;69 }
HDU 1548 A strange lift （Dijkstra）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。