题意：一栋摩天大楼从0层到K层，有N部电梯，每个电梯都有自己的运行速度，此外，对于某个电梯来说，并不是每一层都会停，允许在某一层进行电梯换乘，每次换乘固定消耗60秒，最终求从0层去K层的最短时间，如果不能到达，输出 IMPOSSIBLE
确实是个隐式图问题，建图并不难，只要图建好了，进行最短路即可，难点在于电梯换乘，因为电梯换乘额外消耗60s因此，不能简单的指向该层节点，结果明显不对。。。。所以我自己就想出了一个多线程的最短路，每个电梯独立建一个图，分别以0-99，100-199，200-299.。。。因为最多有五部电梯，因此，只需要最多400-499一共500个点即可，独立图中点是指相同层数，只是百位不同，所以每个相同层的点互相建边，边权为60。
图建好后进行最短路即可
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define INF 1<<30 using namespace std; int g[510][510]; int times[10]; int lift[10][110]; int num[10]; int d[510]; int vis[510]; int n,k; void init() { int i,j; for (i=0;i<=509;i++) { for (j=0;j<=509;j++) { if (i==j) g[i][j]=0; else g[i][j]=INF; } d[i]=INF; } for (i=0;i<=99;i++) { for (j=0;j<n;j++) { for (int w=0;w<n;w++) //把不同电梯的相同层的节点进行连接，权值为60，代表换乘电梯 { if (w==j) continue; g[j*100+i][w*100+i]=60; } } } } void dijstla() { d[500]=0; int i,j; memset(vis,0,sizeof vis); for (i=0;i<=500;i++) { int mini=INF,loc; for (j=0;j<=500;j++) { if (vis[j]) continue; if (mini>d[j]) { mini=d[j]; loc=j; } } vis[loc]=1; for (j=0;j<=500;j++) { if (vis[j]) continue; if (loc==j) continue; if (g[loc][j]>=INF) continue; if (d[j]>d[loc]+g[loc][j]) d[j]=d[loc]+g[loc][j]; } } } int main() { int i,j; while (scanf("%d%d",&n,&k)!=EOF) { for (i=0;i<n;i++) { scanf("%d",×[i]); } for (i=0;i<n;i++) { int cur=0; char ch; while (1){ scanf("%d",&lift[i][cur++]); ch=getchar(); if (ch==‘\n‘) break; } num[i]=cur; sort(lift[i],lift[i]+cur); } init(); for (i=0;i<n;i++) { for (j=0;j<num[i];j++) { for (int w=j+1;w<num[i];w++) { int t1=100*i+lift[i][j]; int t2=100*i+lift[i][w]; g[t1][t2]=g[t2][t1]=(t2-t1)*times[i]; //分别给每个电梯建图 } } } for (i=0;i<n;i++) { if (lift[i][0]==0) g[500][i*100]=0;//为防止0层有多个电梯可达，因此添加500为一个超级原点，500到各0层点权值均为0 } dijstla(); int ans=INF; for (i=0;i<n;i++) { if (ans>d[i*100+k]) ans=d[i*100+k]; } if (ans>=INF) puts("IMPOSSIBLE"); else printf("%d\n",ans); } return 0; }