题目大意：一座楼有100层，编号0-99，有n个电梯，每个电梯有不同的速度，并且只在指定的楼层停，在某一层如果有多个电梯停，在两个电梯间转移需要1分钟，求出从0层出发到达k层的所用的最短时间。

　　本来是正常的单源最短路问题，可是电梯转移花费的时间使得问题复杂了。刚开始是把一个节点扩展成两个节点，一个进一个出，在进出两个节点间加上60s的开销，纠结的好久才憋出来（犯了好多错误...浪费了好长时间），结果却WA了，用别人的测试用例结果也对，忽然就想到可能最终要到0层（写代码时考虑到了，可是认为不会这么干，也就没多写），处理完0之后，就好了...-_-||

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 #define MAXN 210 7 #define INF 1e8 8  9 int G[MAXN][MAXN], dist[MAXN];10 bool vis[MAXN];11 12 int main()13 {14 #ifdef LOCAL15     freopen("in", "r", stdin);16 #endif17     int n, k;18     int time[10];19     while (scanf("%d%d", &n, &k) != EOF)20     {21         for (int i = 0; i < n; i++)22             scanf("%d", &time[i]);23         getchar();24         for (int i = 0; i < 200; i++)25             for (int j = 0; j < 200; j++)26                 G[i][j] = INF;27         for (int i = 0; i < 100; i++)28             G[i*2][i*2+1] = G[i*2+1][i*2] = 60;29         for (int i = 0; i < n; i++)30         {31             char str[10000];32             gets(str);33             vector
          
            v;34             int len = strlen(str);35             for (int j = 0; j < len; j++)36             {37                 if (isdigit(str[j]))38                 {39                     int t = str[j] - '0';40                     j++;41                     while (j < len && isdigit(str[j]))42                     {43                         t = t * 10 + str[j] - '0';44                         j++;45                     }46                     v.push_back(t);47                 }48             }49             for (int j = 0; j < v.size(); j++)50                 for (int p = j+1; p < v.size(); p++)51                 {52                     int x = v[j], y = v[p];53                     G[2*x+1][2*y] = G[2*y+1][2*x] = min(G[2*x+1][2*y], (y-x)*time[i]);54                 }55         }56         memset(vis, 0, sizeof vis);57         for (int i = 0; i < 200; i++)58             dist[i] = INF;59         dist[1] = 0;60         if (k)  k *= 2;61         else  k = 1;62         for (int i = 0; i < 200; i++)63         {64             int u, lmin = INF;65             for (int j = 0; j < 200; j++)66                 if (!vis[j] && dist[j] <= lmin)67                 {68                     lmin = dist[j];69                     u = j;70                 }71             vis[u] = 1;72             if (u == k)  break;73             for (int j = 0; j < 200; j++)74                 dist[j] = min(dist[j], dist[u]+G[u][j]);75         }76         if (dist[k] != INF)  printf("%d\n", dist[k]);77         else  printf("IMPOSSIBLE\n");78     }79     return 0;80 }
          
         
        
       
      

　　后来看到可以不用这么麻烦，也是，上面那个代码构图时考虑了几次才对了。正常构图，在算权重的时候加上60就可以了（从0扩展出来的不用加60）。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 #define MAXN 110 6 #define INF 1e9 7 #define N 100 8 typedef pair
         
           ii; 9 typedef vector
          
            vii;10 11 int G[MAXN][MAXN];12 int time[10];13 14 int main()15 {16 #ifdef LOCAL17     freopen("in", "r", stdin);18 #endif19     int n, k;20     while (scanf("%d%d", &n, &k) != EOF)21     {22         for (int i = 0; i < n; i++)23             scanf("%d", &time[i]);24         for (int i = 0; i < N; i++)25             for (int j = 0; j < N; j++)26                 G[i][j] = INF;27         for (int i = 0; i < n; i++)28         {29             vector
           
             v;30 do31 {32 int x;33 scanf("%d", &x);34 v.push_back(x);35 } while (getchar() != '\n');36 for (int p = 0; p < v.size(); p++)37 for (int q = p+1; q < v.size(); q++)38 {39 int x = v[p], y = v[q];40 G[x][y] = G[y][x] = min(G[x][y], (y-x)*time[i]);41 }42 }43 vector
            
              dist(N, INF);44 dist[0] = 0;45 priority_queue
             
              , greater
              
                > pq;46 pq.push(ii(0, 0));47 while (!pq.empty())48 {49 ii top = pq.top();50 pq.pop();51 int d = top.first, u = top.second;52 if (u == k) break;53 if (d == dist[u])54 for (int v = 0; v < N; v++)55 {56 if (u == 0)57 {58 if (dist[u] + G[u][v] < dist[v])59 {60 dist[v] = dist[u] + G[u][v];61 pq.push(ii(dist[v], v));62 }63 }64 else65 {66 if (dist[u] + G[u][v] + 60 < dist[v])67 {68 dist[v] = dist[u] + G[u][v] + 60;69 pq.push(ii(dist[v], v));70 }71 }72 }73 }74 if (dist[k] != INF) printf("%d\n", dist[k]);75 else printf("IMPOSSIBLE\n");76 }77 return 0;78 }