[UVA 10801]Lift Hopping[Dijkstra][建图]

题目链接：[UVA 10801]Lift Hopping[Dijkstra][建图]

题意分析：

从0层开始，一共有n台电梯供你到达目的地k层。每台电梯往上走一层都要消耗t[i]的时间，并且电梯只能在特定的楼层停下，，换乘电梯要花费60s的时间，而且呢，你不能用楼梯上楼，只能搭电梯。。。。（hentai！）问：最快到达楼层k的时间是多少？不能到达就输出-1。

解题思路：

这题技巧就是体现在建图上，图建好了，用dijkstra跑一遍就行了。

具体建图就是用mp[i][j]代表从楼层i到楼层j的最小距离。这里不考虑换乘，先这样把图建好。

对于换乘，我们在dijkstra更新节点的时候使用。具体为：d[y] = min(d[y], d[x] + mp[x][y] + 60);

这里更新时加上60s的具体理由在于：这里我们默认第一次进电梯算是换乘，所以加上60s。这样不管是一路搭到底（每个d[i]都加60，一起比较起来没有影响），还是有换乘（本来就该加60s嘛）。都不会影响。

这样在计算最终结果时，减去60就是最终的结果了（因为默认了第一次进入电梯算换乘）。

个人感受：

感觉好神奇的建图~

具体代码如下：

#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<sstream>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f, MAXN = 111;int t[MAXN], mp[MAXN][MAXN], floors[MAXN], len, vis[MAXN], d[MAXN], n, k;string s;void build(int node){for (int i = 0; i < len; ++i)for (int j = i + 1; j < len; ++j){int &a = floors[j], &b = floors[i];int dis = (a – b) * t[node];if (dis < mp[b][a])mp[a][b] = mp[b][a] = dis;}}void dijkstra(){memset(vis, 0, sizeof vis);memset(d, 0x3f, sizeof d);d[0] = 0;for (int i = 0; i < 100; ++i){int x, mx = INF;for (int y = 0; y < 100; ++y) if(!vis[y] && d[y] <= mx) mx = d[x = y];vis[x] = 1;for (int y = 0; y < 100; ++y) d[y] = min(d[y], d[x] + mp[x][y] + 60);}if (d[k] == INF)cout << "IMPOSSIBLE\n";elsecout << max(0, d[k] – 60) << '\n';//小心目标楼层为0的情况}int main(){while(~scanf("%d%d", &n, &k)){memset(mp, 0x3f, sizeof mp);for (int i = 0; i < n; ++i)scanf("%d", &t[i]);getchar();for (int i = 0; i < n; ++i){len = 0;int x;getline(cin, s);stringstream ss(s);while (ss >> x){floors[len++] = x;}build(i);}dijkstra();}return 0;}

版权声明：欢迎转载(^ω^)~不过转载请注明原文出处： ()

人若软弱就是自己最大的敌人