UVa10801 - Lift Hopping

本文主要是介绍UVa10801 - Lift Hopping，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        题意：一栋摩天楼（0~99层）有n个电梯。每个电梯的速度是不一样的，第i个电梯运行（上下）一层要花Ti秒，每个电梯只在某些楼层停，换电梯需要等1分钟。你现在在0层，去往k层，问最少要花多少时间。

        思路：SPFA求最短路。

        不过这个题建图不是那么好建，索性不建图了。我联想到了平行宇宙。。。假设这个楼在5个世界里都存在。。“穿越”到另一个世界需要花一分钟。。。好吧。。我的方法是把楼视为有500层，第一个电梯只能去0~99层，第二个电梯100~199，其他的类推。然后把那些电梯能停的楼层标记出来，写一个函数计算状态转移的时间，就可以从起点开始SPFA了，详见代码。

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <vector>
#include <queue>
#include <stack>
#include <ctype.h>
#define INF 1000000000
using namespace std;int T[5];//每个电梯上下一楼时间 
bool enable[510];
int ans[510];int time(int f1,int f2){int e1=f1/100;int e2=f2/100;if(e1==e2){return abs(f1-f2)*T[e1];}else{if(!(f1%100)){return 0;}else{return 60;}}
}int main(){int n,k;while(cin>>n>>k){memset(enable,0,sizeof(enable));for(int i=0;i<510;i++)ans[i]=INF;for(int i=0;i<5;i++)ans[i*100]=0;for(int i=0;i<n;i++){cin>>T[i];}for(int i=0;i<n;i++){int j;while(cin>>j){enable[j+i*100]=true;if(getchar()=='\n')break;}}queue<int> que;if(enable[0])que.push(0);//入队的时候不能少了if(enable[100])que.push(100);if(enable[200])que.push(200);if(enable[300])que.push(300);if(enable[400])que.push(400);while(!que.empty()){int cur=que.front();int e=cur/100;int f=cur%100;que.pop();for(int i=e*100;i<(e+1)*100;i++){if(enable[i]){if( (ans[cur]+time(cur,i))<ans[i] ){ans[i]=(ans[cur]+time(cur,i));que.push(i);}}}for(int i=0;i<5;i++){if(enable[i*100+f]){if( (ans[cur]+time(cur,i*100+f))<ans[i*100+f] ){ans[i*100+f]=(ans[cur]+time(cur,i*100+f));que.push(i*100+f);}}}}int t=INF;for(int i=0;i<5;i++){if(ans[i*100+k]<t){t=ans[i*100+k];}}if(t==INF){cout<<"IMPOSSIBLE"<<endl;}else{cout<<t<<endl;}}return 0;
}

这篇关于UVa10801 - Lift Hopping的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---