本文主要是介绍uva 10801（乘电梯dijkstra），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给几个电梯，电梯0 ~ n-1分别可以到达很多层楼。
换乘电梯需要60s时间。
问从0层到target层最小的时间。
解析：
将进入第0层的电梯60s也算上，最后减。
坑点是如果target为0输出0。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long longusing namespace std;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double pi = 4 * atan(1.0);
const double ee = exp(1.0);int n, target;
int Time[maxn], tot;
int g[maxn][maxn], Index[maxn];
int dis[maxn];
bool vis[maxn];void readGraph(int x)
{for (int i = 0; i < tot; i++){for (int j = 0; j < tot; j++){if (i != j){int t = abs(Index[i] - Index[j]) * Time[x];if (t < g[Index[i]][Index[j]])g[Index[i]][Index[j]] = g[Index[j]][Index[i]] = t;}}}
}void dijkstra()
{memset(vis, false, sizeof(vis));memset(dis, inf, sizeof(dis));dis[0] = 0;vis[0] = true;for(int i = 0; i < 100; i++){int mark = 0, mindis = inf;for(int j = 0; j < 100; j++){if(!vis[j] && dis[j] < mindis){mindis = dis[j];mark = j;}}vis[mark] = true;for(int j = 0; j < 100; j++){if (!vis[j]){dis[j] = min(dis[j], dis[mark] + g[mark][j] + 60);}}}
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d", &n, &target)){memset(g, inf, sizeof(g));memset(Time, 0, sizeof(Time));memset(Index, 0, sizeof(Index));for (int i = 0; i < n; i++){scanf("%d", &Time[i]);}for (int i = 0; i < n; i++){memset(Index, 0, sizeof(Index));tot = 0;do{scanf("%d", &Index[tot++]);}while (getchar() != '\n');readGraph(i);}dijkstra();if (dis[target] == inf)printf("IMPOSSIBLE\n");else{if (target == 0)printf("0\n");elseprintf("%d\n", dis[target] - 60);}}return 0;
}
这篇关于uva 10801（乘电梯dijkstra）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
