UVa Q10841

#include <bits/stdc++.h>
using namespace std;

struct stat{
    int fl, elv, T;
    bool operator>(const stat &x)const{return T > x.T;}
};
int times[50];
bool vis[50][100];
vector<int> stop[50];
vector<int> mov[100];

int32_t main(){
    int n,k;
    while(cin >> n >> k){
        for(int i = 0; i < n; ++i)cin >> times[i];
        for(int i = 0; i < 100; ++i)mov[i].clear();
        for(int i = 0; i < 50; ++i)stop[i].clear();
        memset(vis, 0, sizeof(vis));
        cin.get();
        for(int i = 0; i < n; ++i){
            string in;
            stringstream ss;
            getline(cin, in);
            ss << in;
            int x;
            while(ss >> x){
                stop[i].emplace_back(x);
                mov[x].emplace_back(i);
            }
        }
        priority_queue<stat, deque<stat>, greater<stat>> pq;
        stat tmd = {.fl = 0, .elv = 0, .T = 0};
        for(tmd.elv = 0; tmd.elv < n; ++tmd.elv){
            if(stop[tmd.elv][0] == 0){
                if(k != 0)tmd.T = stop[tmd.elv].back() * times[tmd.elv];
                pq.push(tmd);
            }
        }
        int ans = -1;
        while(!pq.empty()){
            tmd = pq.top();
            pq.pop();
            if(tmd.fl == k){
                ans = tmd.T;
                break;
            }
            if(vis[tmd.elv][tmd.fl])continue;
            vis[tmd.elv][tmd.fl] = 1;
            //cout << tmd.fl << ' ' << tmd.elv << ' ' << tmd.T << endl;
            for(unsigned i = 0; i < stop[tmd.elv].size(); ++i){//change floor
                if(!vis[tmd.elv][stop[tmd.elv][i]]){
                    stat nxt;
                    nxt.fl = stop[tmd.elv][i];
                    nxt.elv = tmd.elv;
                    nxt.T = tmd.T + times[tmd.elv] * abs(nxt.fl-tmd.fl);
                    pq.push(nxt);
                    //cout << ' ' << nxt.fl << ' ' << nxt.elv << ' ' << nxt.T << endl;
                }
            }
            for(unsigned i = 0; i < mov[tmd.fl].size(); ++i){
                if(!vis[mov[tmd.fl][i]][tmd.fl]){
                    stat nxt;
                    nxt.fl = tmd.fl;
                    nxt.elv = mov[tmd.fl][i];
                    nxt.T = tmd.T + 5 + times[nxt.elv] * max(abs(stop[nxt.elv][0] - nxt.fl), abs(stop[nxt.elv].back() - nxt.fl));
                    pq.push(nxt);
                    //cout << ' ' << nxt.fl << ' ' << nxt.elv << ' ' << nxt.T << endl;
                }
            }
        }
        if(ans == -1)cout << "IMPOSSIBLE\n";
        else cout << ans << '\n';
    }
    return 0;
}