uva 10801 Lift Hopping

最短路

题意：有一栋楼100层，从0到99编号层数，有多部电梯（最多5部），给出每部每部电梯的速度，即上或下一层楼所用的秒数。然后每部电梯不一定在所有楼层出现，给你所有电梯可能出现的层数。给你一个目标层，要你从0层开始到目标层，问所用时间最短。在0层的时候选择做哪步电梯出发不需要时间的，但是在中间的楼层，想换电梯的时候，需要60秒

这个题目看完就可以想到是最短路，每层楼是1个顶点，一共100个点，然后对于楼层而言可以通过电梯到达的话就是有一条边，权值就是时间，那么可能出现平行边，比如1号电梯可以从10楼到20楼，用时200秒，2号电梯也可以从10到20楼用时100秒……………………

这题，一开始没想那么多，用了邻接表来建图做，然后sample不过，然后调试一下发现了转换电梯的时候会出错，然后思考了很久不知道怎么搞

一般的最短路其实都基于一个性质就是都符合最优子结构的，但是这道题其实不符合最优子结构，因为轮换增加的60秒破坏了最优子结构，看sample1的数据就可以知道，从0到30楼是要经过15楼的，但是去15的时候却不是最短的，我们是用2号电梯到达15楼，但是如果要去15楼的时间最短那么应该是坐1号电梯，但是如果坐了1号电梯到15楼将无法满足到30楼的时间最短，这其实有种为了最后的目标的最优解而舍近求远的感觉

 

后来想了一下，想了其实用邻接表来建图本身就是一个失败的旋转，如果是用邻接矩阵来建图，那么整个问题就变得很简单

所以这个题目让我想到师兄之前说的一句话，做图论讲究经验，尤其是什么问题有什么来建图这个很关键，这次算是体会到了

 

我写了3个版本，第一个普通的dij+邻接矩阵 ， 第二个spfa+邻接矩阵 ， 第三个优先队列dij+邻接矩阵

3个版本只是改了求最短路的函数，读取数据和建图函数是一样，都是邻接矩阵建图

至于为什么这样建图很难文字描述，可以仔细看第一份代码的建图（后面的建图是一样的），看代码反而更容易懂

 

然后要AC还要注意三点

1.终点楼层可能就是0层，所以要特殊判断，输出0。

2.三个代码中都是算多了一个60秒，就是从0层出发的时候算多一个60秒，但是题目说不用的，所以最后答案减去1个60

3.三个代码松弛都是 d[u]+g[u][v]+60 < d[v]  ，  并不是说换不换电梯都加60，而是在换电梯的时候才+60，为什么呢，看懂了建图部分这个就懂了

 

第一个普通的dij+邻接矩阵

#include <cstdio> #include <cstring> #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //邻接矩阵建图 }return ; } void dij() {int fin[N];memset(d,0x3f,sizeof(d));memset(fin,0,sizeof(fin));d[s=0]=0;for(int nn=0; nn<99; nn++) //进行n-1次 {int min=INF,u=s,flag=0;for(int i=0; i<=99; i++)if(!fin[i] && d[i]<min){ min=d[i]; u=i; flag=1; }if(!flag) break; //已经找不到了即结束了fin[u]=1;for(int v=0; v<=99; v++) //松弛if(!fin[v] && d[u]+g[u][v]+60 < d[v])d[v]=d[u]+g[u][v]+60;}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60); } int main() {while(scanf("%d%d",&n,&t)!=EOF){input();dij(); //dij邻接矩阵 }return 0; }

 

 

 第二个spfa+邻接矩阵

#include <cstdio> #include <cstring> #include <queue> using namespace std; #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //邻接矩阵建图}return ; }void spfa() {queue<int> q;int vis[N];memset(vis,0,sizeof(vis));memset(d,0x3f,sizeof(d));d[s=0]=0; vis[s]=1;q.push(s);while(!q.empty()){int u=q.front(); vis[u]=0; q.pop();for(int v=0; v<=99; v++)if(d[u]+g[u][v]+60 < d[v]){d[v]=d[u]+g[u][v]+60;if(!vis[v]){q.push(v);vis[v]=1;}}}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60);} int main() {while(scanf("%d%d",&n,&t)!=EOF){input();spfa();}return 0; }

 

 

第三个优先队列dij+邻接矩阵

#include <cstdio> #include <cstring> #include <queue> #include <utility> #include <vector> using namespace std; #define N 110 #define INF 0x3f3f3f3f int g[N][N],d[N],sp[10]; int s,t,n; typedef pair<int , int> pii;void graph(int k,int ccount , int *m) {for(int i=1; i<=ccount; i++)for(int j=i+1; j<=ccount; j++){int u=m[i],v=m[j],w=(v-u)*sp[k];if(w<g[u][v])g[u][v]=g[v][u]=w;}return ; } void input() {int m[N],ccount; char ch;memset(g,0x3f,sizeof(g));for(int i=1; i<=n; i++) scanf("%d",&sp[i]);for(int i=1; i<=n; i++){ccount=0;while(1){scanf("%d",&m[++ccount]);ch=getchar();if(ch=='\n')break;}//for(int j=1; j<=ccount; j++)//printf("%d ",m[j]);//printf("\n");graph(i,ccount,m); //邻接矩阵建图}return ; }void dij() {priority_queue<pii,vector<pii>,greater<pii> > q; //优先队列3个参数,变量类型，容器类型，比较算子int fin[N];memset(fin,0,sizeof(fin));memset(d,0x3f,sizeof(d));d[s=0]=0;q.push(make_pair(d[s],s));while(!q.empty()){pii p; int u;p=q.top(); q.pop();u=p.second; //点的标号if(fin[u]) continue; //该点已经计算过fin[u]=1; for(int v=0; v<=99; v++) //松弛if( d[u]+g[u][v]+60 < d[v] ){d[v]=d[u]+g[u][v]+60;q.push(make_pair(d[v],v));}}if(d[t]==INF)printf("IMPOSSIBLE\n");else if(t==s)printf("0\n");elseprintf("%d\n",d[t]-60); }int main() {while(scanf("%d%d",&n,&t)!=EOF){input();dij(); //dij优先队列}return 0; }

 

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的uva 10801 Lift Hopping的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。