uva 10801 - Lift Hopping(最短路Dijkstra)

/*
   题目大意：
      就是一幢大厦中有0～99的楼层, 然后有1～5个电梯！每个电梯有一定的上升或下降速度和楼层的停止的位置！
      问从第0层楼到第k层最少经过多长时间到达！
      
   思路：明显的Dijkstra ，在建图的时候u->v可能有多个电梯到达，取时间最少的当作路径的权值！ 
   如果我们发现 d[i] > d[j] + map[j][i] + 60, 那么说明从第0层到达第 i 层的时间大于从第j层
   转移到其他电梯然后到达第 i 层的时间，那么就更新d[i]的值！ 
       
*/
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
int map[105][105];
int d[105];
int t[5];
int lift[105];
int vis[105];
int n, k;

void addEdge(int a, int b, int tt){
    int dist=abs(a-b)*tt;
    if(map[a][b]>dist)
       map[a][b]=map[b][a]=dist;
}

void Dijkstra(){
    int root=0, p;
    memset(vis, 0, sizeof(vis));
    vis[0]=1;
    for(int i=1; i<=99; ++i){
        int minLen=INF;
        for(int j=1; j<=99; ++j){
           if(!vis[j] && d[j] > d[root]+map[root][j]+60)
              d[j] = d[root]+map[root][j]+60;
           if(!vis[j] && minLen>d[j]){
              minLen=d[j];
              p=j; 
           }
        }
        if(minLen==INF)
           return ;
        root=p;
        vis[root]=1; 
    } 
} 

int main(){
   while(scanf("%d%d", &n, &k)!=EOF){
          memset(map, 0x3f, sizeof(map));
          memset(d, 0x3f, sizeof(d));
          d[0]=0;
       for(int i=1; i<=n; ++i)
          scanf("%d", &t[i]);
       char ch;
       
       for(int i=1; i<=n; ++i){
           int cnt=0;
           while(1){
              scanf("%d%c", &lift[cnt++], &ch);
              for(int j=0; j<cnt-1; ++j)
                  addEdge(lift[cnt-1], lift[j], t[i]);
                  
              if(ch=='\n')
                 break; 
           }
       } 
       
       Dijkstra();
       
       if(k==0)
          printf("0\n");       
       else if(d[k]!=INF)
          printf("%d\n", d[k]-60);
       else printf("IMPOSSIBLE\n"); 
   }
   return 0;
}