链接：http://vjudge.net/problem/viewProblem.action?id=22172

描述：有n部电梯，每部电梯都有不能停下的楼层，要求搭乘电梯从第0层到第k层。

思路：单源点最短路

        建图：将每层楼拆成n个点，用边权解决换乘等待的时间。将每部电梯能到达的楼层顺次连接，边权是该电梯经过所需时间。最后建立一个超级源点S，连接每部电梯的第0层的节点，边权为0，方便统计答案。

 

下面是我的实现，Dijkstra版本：

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            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
          
           b.dist; 70     } 71 }; 72 priority_queue 
           
            , 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 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            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
          

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 }