首页 > 代码库 > [题解]UVA10801 Lift Hopping
[题解]UVA10801 Lift Hopping
链接：http://vjudge.net/problem/viewProblem.action?id=22172
描述：有n部电梯，每部电梯都有不能停下的楼层，要求搭乘电梯从第0层到第k层。
思路：单源点最短路
建图：将每层楼拆成n个点，用边权解决换乘等待的时间。将每部电梯能到达的楼层顺次连接，边权是该电梯经过所需时间。最后建立一个超级源点S，连接每部电梯的第0层的节点，边权为0，方便统计答案。
下面是我的实现，Dijkstra版本：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 #define MaxN 520 7 #define MaxM 3020 8 #define Max_n 8 9 #define S 500 10 #define INF 100000 11 struct node 12 { 13 int v,dist; 14 node *next; 15 }; 16 node Edge[MaxM]; 17 node *cnt=&Edge[0]; 18 node *adj[MaxN]; 19 int dist[MaxN]; 20 int T[Max_n]; 21 int n,K,Ans; 22 bool For_Build[MaxN]; 23 inline void Clean() 24 { 25 memset(Edge,0,sizeof(Edge)); 26 cnt=&Edge[0]; 27 memset(adj,0,sizeof(adj)); 28 } 29 inline void Addedge(int u,int v,int w) 30 { 31 node *p=++cnt; 32 p->v=v; 33 p->dist=w; 34 p->next=adj[u]; 35 adj[u]=p; 36 37 p=++cnt; 38 p->v=u; 39 p->dist=w; 40 p->next=adj[v]; 41 adj[v]=p; 42 } 43 inline void Read_Build() 44 { 45 int i,j,Num,f1,f2; 46 for(i=1;i<=n;i++) 47 scanf("%d",&T[i]); 48 for(i=1;i<=n;i++) 49 { 50 Num=100*(i-1); 51 Addedge(S,Num,0); 52 f1=-1; 53 do 54 { 55 scanf("%d",&f2);For_Build[Num+f2]=true; 56 if(f1!=-1) 57 Addedge(Num+f1,Num+f2,(f2-f1)*T[i]); 58 f1=f2; 59 for(j=1;j<i;j++) 60 if(For_Build[100*(j-1)+f2]) 61 Addedge(100*(j-1)+f2,Num+f2,60); 62 }while(getchar()!=‘\n‘); 63 } 64 } 65 struct cmp 66 { 67 bool operator()(node a,node b) 68 { 69 return a.dist>b.dist; 70 } 71 }; 72 priority_queue <node, vector<node>, cmp> q; 73 void Dijkstra(int s) 74 { 75 node c,d; 76 node *p; 77 int i,j,k; 78 memset(dist,0x3f,sizeof(dist)); 79 dist[s]=0; 80 c.v=s;c.dist=0; 81 q.push(c); 82 while(!q.empty()) 83 { 84 d=q.top();q.pop(); 85 j=d.v; 86 for(p=adj[j];p!=NULL;p=p->next) 87 { 88 k=p->v; 89 if(dist[k]>dist[j]+p->dist) 90 { 91 dist[k]=dist[j]+p->dist; 92 d.v=k;d.dist=dist[k]; 93 q.push(d); 94 } 95 } 96 } 97 } 98 inline void Print() 99 {100 int i;101 for(i=1;i<=n;i++)102 Ans=min(Ans,dist[100*(i-1)+K]);103 if(Ans==INF)104 printf("IMPOSSIBLE\n");105 else106 printf("%d\n",Ans);107 }108 int main()109 {110 while(scanf("%d%d",&n,&K)!=EOF)111 {112 Clean();113 Read_Build();114 Dijkstra(S);115 Ans=INF;116 Print();117 }118 return 0;119 }
我是用拆点的方法解决换乘等待的时间问题的，在网上看到另一种处理方式感觉很科学。本以为我的会很慢，实践证明还是算比较快的了，也可能是数据不强。
然后我再试了试spfa，稍微慢一点：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 #define MaxN 520 7 #define MaxM 3020 8 #define Max_n 8 9 #define S 500 10 #define INF 100000 11 struct node 12 { 13 int v,dist; 14 node *next; 15 }; 16 node Edge[MaxM]; 17 node *cnt=&Edge[0]; 18 node *adj[MaxN]; 19 int dist[MaxN]; 20 int T[Max_n]; 21 int n,K,Ans; 22 bool For_Build[MaxN],vis[MaxN]; 23 inline void Clean() 24 { 25 memset(Edge,0,sizeof(Edge)); 26 cnt=&Edge[0]; 27 memset(adj,0,sizeof(adj)); 28 } 29 inline void Addedge(int u,int v,int w) 30 { 31 node *p=++cnt; 32 p->v=v; 33 p->dist=w; 34 p->next=adj[u]; 35 adj[u]=p; 36 37 p=++cnt; 38 p->v=u; 39 p->dist=w; 40 p->next=adj[v]; 41 adj[v]=p; 42 } 43 inline void Read_Build() 44 { 45 int i,j,Num,f1,f2; 46 for(i=1;i<=n;i++) 47 scanf("%d",&T[i]); 48 for(i=1;i<=n;i++) 49 { 50 Num=100*(i-1); 51 Addedge(S,Num,0); 52 f1=-1; 53 do 54 { 55 scanf("%d",&f2);For_Build[Num+f2]=true; 56 if(f1!=-1) 57 Addedge(Num+f1,Num+f2,(f2-f1)*T[i]); 58 f1=f2; 59 for(j=1;j<i;j++) 60 if(For_Build[100*(j-1)+f2]) 61 Addedge(100*(j-1)+f2,Num+f2,60); 62 }while(getchar()!=‘\n‘); 63 } 64 } 65 queue<int>q; 66 void Spfa(int s) 67 { 68 int j,k; 69 memset(dist,0x3f,sizeof(dist)); 70 dist[s]=0; 71 q.push(s); 72 vis[s]=true; 73 while(!q.empty()) 74 { 75 j=q.front(); 76 q.pop(); 77 vis[j]=false; 78 for(node *p=adj[j];p!=NULL;p=p->next) 79 { 80 k=p->v; 81 if(dist[k]>dist[j]+p->dist) 82 { 83 dist[k]=dist[j]+p->dist; 84 if(!vis[k]) 85 { 86 q.push(k); 87 vis[k]=true; 88 } 89 } 90 } 91 } 92 } 93 inline void Print() 94 { 95 int i; 96 for(i=1;i<=n;i++) 97 Ans=min(Ans,dist[100*(i-1)+K]); 98 if(Ans==INF) 99 printf("IMPOSSIBLE\n");100 else101 printf("%d\n",Ans);102 }103 int main()104 {105 while(scanf("%d%d",&n,&K)!=EOF)106 {107 Clean();108 Read_Build();109 Spfa(S);110 Ans=INF;111 Print();112 }113 return 0;114 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。