Solution UVA: 10801 - Lift Hopping

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10801 - Lift Hopping	Accepted	C++11	0.000	0.000	1433	49 secs ago

Suggest:

- This is fucking hard dijkstra problem have implenment that i used to code (by my method) 

-> So you can choose another method maybe easy than it (i was research and find many but i can't understand so I have to think and code by myself )

Below is method like me (from codeforces):

This problem is more about carefully modelling graph. There can be different ways to model the graph, I used the following which looks intuitive to me. Once we model the graph, the problem is just single shortest path problem and which can be solved using Dijkstra.
Nodes: each node is pair( elevator, floor). Edges: For edges with in same floor, weight= dist*time. For edges across elevators stopping at same floor weight=switch-time, which in this problem is 60.
Following example with clarify better:
3 50
10 50 100
0 10 30 40
0 20 30
0 20 50

#include<bits/stdc++.h>

#define X first

#define Y second

#define long long long

#define mp make_pair

#define pb push_back

#define FOR(i, a, b) for(long i=a; i<=b; i++)

using namespace std;

typedef pair<long, long> ii;

typedef pair<ii, long> iii;

const long oo=(long)1e18;

const int N=1000111;

long n,m;

long k,u,l,v, K;

map<ii,long> d;

map<ii, vector<iii>> a;

int va[N];

string s;

vector< vector<long> > vec;

vector<long> process(string s){

    string x="";

    vector<long> a;

    while(s[0] == ' ') s.erase(0);

    while(s[s.size()-1] == ' ') s.erase(s.size()-1);

    s+=' ';

    for(int i=0; s[i]; i++){

        if (s[i]==' '){

            a.push_back(stoi(x));

            x="";

        }

        else x += s[i];

    }

    return a;

}

void reset(){

    a.clear();

    vec.clear();

    d.clear();

}

 void Dijkstra_heap(){

     //parent[ii(1,0)]= ii(-1,-1);

     for(auto it=a.begin(); it!=a.end(); it++)

        d[it->X]= oo;

     d[ii(-1,-1)]= 0;

     d[ii(0,0)]= oo;

     priority_queue< pair<long, ii> > Q;

     Q.push(mp(-d[ii(-1,-1)], ii(-1,-1)));

     while(Q.size()){

         long du=-Q.top().first;

         ii u= Q.top().second;

         Q.pop();

         if (du > d[u]) continue;

         for(iii p:a[u]){

              ii v=p.X; long val=p.Y;

             if (d[v] > d[u] + val){

                 d[v] = d[u] + val;

                 //parent[v] = u;

                 //check[v]= d[v];

                 Q.push(mp(-d[v], v));

             }

         }

     }

     if (d[ii(0,0)] == oo) cout<<"IMPOSSIBLE\n";

        else cout<<d[ii(0,0)]<<"\n";

     //find_path(ii(0,0));

 }

void Scanf(){

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    while(cin >> n >> K){

        reset();

        vec.pb(vector<long>(1));

        FOR(i, 1, n) cin >> va[i];

        cin.ignore();

        FOR(i, 1, n){

            getline(cin, s);

            vec.pb(process(s));

        }

        FOR(l, 1, n){

            vector<long> vt = vec[l];

            for(int i=0; i<vt.size()-1; i++)

                for(int j=i+1; j<vt.size(); j++){

                    ii p = ii(l, i+1);

                    ii q = ii(l, j+1);

                    long dis = abs(vt[j] - vt[i])*va[l];

                    iii pp = iii(p, dis);

                    iii qq = iii(q, dis);

                    a[p].pb(qq);

                    a[q].pb(pp);

                }

        }

        FOR(i1, 1, n-1)

        FOR(i2, i1+1, n){

            vector<long> v1 = vec[i1];

            vector<long> v2 = vec[i2];

            for(int i=0; i<v1.size(); i++)

                for(int j=0; j<v2.size(); j++)

                    if (v1[i] == v2[j]){

                    ii p = ii(i1, i+1);

                    ii q = ii(i2, j+1);

                    long dis = 60;

                    iii pp = iii(p, dis);

                    iii qq = iii(q, dis);

                    a[p].pb(qq);

                    a[q].pb(pp);

                }

        }

        FOR(l, 1, n){

            vector<long> vv = vec[l];

            for(int i=0; i<vv.size(); i++)

            if (vv[i]==K) {

                    ii p = ii(l, i+1);

                    ii q = ii(0, 0);

                    long dis = 0;

                    iii pp = iii(p, dis);

                    iii qq = iii(q, dis);

                    a[p].pb(qq);

                    a[q].pb(pp);

            }

        }

        FOR(j, 1, n){

        ii p = ii(j, 0);

         vector<long> vt = vec[j];

         if (vt[0] != 0) continue;

         a[ii(-1,-1)].pb(iii(ii(j,1), 0));

         a[ii(j,1)].pb(iii(ii(-1,-1), 0));

         for(int i=0; i<vt.size(); i++){

                ii q = ii(1, i+1);

                long dis = vt[i]*va[j];

                iii pp = iii(p, dis);

                iii qq = iii(q, dis);

                a[p].pb(qq);

                a[q].pb(pp);

         }

        }

//      for(auto it=a.begin(); it!=a.end(); it++){

//

//          cout<<it->X.X<<" "<<it->X.Y<<"\n";

//          for(auto x:it->Y) cout<<x.X.X<<","<<x.X.Y<<":"<<x.Y<<" ; ";

//

//          cout<<"\n";

//      }

        Dijkstra_heap();

    }

}

//map<ii, ii> parent;

//map<ii, long> check;

//

//void find_path(ii u){

//    if (u.X==-1 && u.Y==-1) return;

//    find_path(parent[u]);

//    cout<<u.X<<","<<u.Y<<":"<<check[u]<<" --> ";

//}

int main(){

    Scanf();

}