10801 - Lift Hopping

 //la solución es hacer un dijkstra, intentando todas las posibilidades
// en cada piso, intentamos ir a todos los otros posibles pisos sin verificar //nada

#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <sstream>
using namespace std;
#define inf 1000000

int main(){
 int n,k;
 while(cin>>n>>k){
    vector<int> time(n);//la velocidad de cada elevador
    for(int i=0;i<n;i++) cin>>time[i];
  
    vector<vector<int> > elev(n);//este arreglo contiene todos los pisos accesables por el elevador i
    vector<vector<int> > flo(100);//este arreglo contiene todos los elevadores que paran en el piso i
    string cad;
      getline(cin,cad); //para corregir la linea vacia
    
    //se llenan todas las adyacencias
    for(int i=0;i<n;i++){
    
      getline(cin,cad);
      istringstream is(cad);
      int x;
      while(is>>x){
    elev[i].push_back(x);
    flo[x].push_back(i);
      }
    }
  
    //soluciones
    vector<int> sol(100,inf);
    sol[0]=0;
  
    //estado: tiempo,piso
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater< pair<int,int> > > q;
    q.push(make_pair(0,0));
    int res=-1;
  
    while(!q.empty()){
     int fl=q.top().second;//piso actual
     int tim=q.top().first;//tiempo actual
     q.pop();
     if(tim>sol[fl]) continue;//si este estado no tiene sentido
     if(fl==k){res=tim;break;}//si se llegó a la solución
   
     for(int i=0;i<flo[fl].size();i++){
      int el=flo[fl][i];//elevador que llega al piso fl
    
      for(int j=0;j<elev[el].size();j++){ //se intenta ir a todos los pisos accesables por este elevador, no se hace ninguna verificacion
    int next=elev[el][j]; //siguiente piso
    int ntime=tim+60+abs(next-fl)*time[el]; //nuevo tiempo
    //ojo que el primer elevador que tomemos no tendrá penalidad de tiempo, eso lo vemos en el output
    if(sol[next]>ntime){//si se relaja
      sol[next]=ntime;
      q.push(make_pair(ntime,next));
    }
      }
    
     }
    }
  
    if(res==-1) cout<<"IMPOSSIBLE"<<endl;
    else cout<<(k!=0?res-60:0)<<endl;//si k!=0, entonces, corregimos el tiempo por la penalidad que le pusimos al primer elevador

 }
}