SHARE
TWEET

UVa Q10841

ccbeginner Jan 26th, 2020 (edited) 118 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct stat{
  5.     int fl, elv, T;
  6.     bool operator>(const stat &x)const{return T > x.T;}
  7. };
  8. int times[50];
  9. bool vis[50][100];
  10. vector<int> stop[50];
  11. vector<int> mov[100];
  12.  
  13. int32_t main(){
  14.     int n,k;
  15.     while(cin >> n >> k){
  16.         for(int i = 0; i < n; ++i)cin >> times[i];
  17.         for(int i = 0; i < 100; ++i)mov[i].clear();
  18.         for(int i = 0; i < 50; ++i)stop[i].clear();
  19.         memset(vis, 0, sizeof(vis));
  20.         cin.get();
  21.         for(int i = 0; i < n; ++i){
  22.             string in;
  23.             stringstream ss;
  24.             getline(cin, in);
  25.             ss << in;
  26.             int x;
  27.             while(ss >> x){
  28.                 stop[i].emplace_back(x);
  29.                 mov[x].emplace_back(i);
  30.             }
  31.         }
  32.         priority_queue<stat, deque<stat>, greater<stat>> pq;
  33.         stat tmd = {.fl = 0, .elv = 0, .T = 0};
  34.         for(tmd.elv = 0; tmd.elv < n; ++tmd.elv){
  35.             if(stop[tmd.elv][0] == 0){
  36.                 if(k != 0)tmd.T = stop[tmd.elv].back() * times[tmd.elv];
  37.                 pq.push(tmd);
  38.             }
  39.         }
  40.         int ans = -1;
  41.         while(!pq.empty()){
  42.             tmd = pq.top();
  43.             pq.pop();
  44.             if(tmd.fl == k){
  45.                 ans = tmd.T;
  46.                 break;
  47.             }
  48.             if(vis[tmd.elv][tmd.fl])continue;
  49.             vis[tmd.elv][tmd.fl] = 1;
  50.             //cout << tmd.fl << ' ' << tmd.elv << ' ' << tmd.T << endl;
  51.             for(unsigned i = 0; i < stop[tmd.elv].size(); ++i){//change floor
  52.                 if(!vis[tmd.elv][stop[tmd.elv][i]]){
  53.                     stat nxt;
  54.                     nxt.fl = stop[tmd.elv][i];
  55.                     nxt.elv = tmd.elv;
  56.                     nxt.T = tmd.T + times[tmd.elv] * abs(nxt.fl-tmd.fl);
  57.                     pq.push(nxt);
  58.                     //cout << ' ' << nxt.fl << ' ' << nxt.elv << ' ' << nxt.T << endl;
  59.                 }
  60.             }
  61.             for(unsigned i = 0; i < mov[tmd.fl].size(); ++i){
  62.                 if(!vis[mov[tmd.fl][i]][tmd.fl]){
  63.                     stat nxt;
  64.                     nxt.fl = tmd.fl;
  65.                     nxt.elv = mov[tmd.fl][i];
  66.                     nxt.T = tmd.T + 5 + times[nxt.elv] * max(abs(stop[nxt.elv][0] - nxt.fl), abs(stop[nxt.elv].back() - nxt.fl));
  67.                     pq.push(nxt);
  68.                     //cout << ' ' << nxt.fl << ' ' << nxt.elv << ' ' << nxt.T << endl;
  69.                 }
  70.             }
  71.         }
  72.         if(ans == -1)cout << "IMPOSSIBLE\n";
  73.         else cout << ans << '\n';
  74.     }
  75.     return 0;
  76. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top