Advertisement
tievo

Untitled

Jun 27th, 2024
507
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <sstream>
  5. #include <queue>
  6. #include <climits>
  7.  
  8. using namespace std;
  9.  
  10. #define MAX_FLOOR 100
  11. #define MAX_ELEVATORS 5
  12.  
  13. struct Node {
  14.     int floor;
  15.     int elevator;
  16.     int T;
  17.  
  18.     int dist(const Node& other) const {
  19.        
  20.         if (elevator != other.elevator && floor == other.floor) {
  21.             return 60;
  22.         } else if (elevator == other.elevator) {
  23.             return abs(floor - other.floor) * T;
  24.         } else {
  25.             return INT_MAX;
  26.         }
  27.     }
  28.  
  29.     Node(int floor, int elevator, int T) : floor(floor), elevator(elevator), T(T) {}
  30.  
  31.     bool operator<(const Node& other) const {
  32.         return dist(other) < 0;
  33.     }
  34. };
  35.  
  36. struct NodeComparator {
  37.     bool operator()(const Node& a, const Node& b) const {
  38.         return a.dist(b) > 0; // Using '>' to create a min-heap
  39.     }
  40. };
  41.  
  42. #define Graph vector<vector<Node>>
  43.  
  44.  
  45.  
  46. int dijkstra(Graph& graph, int n, int floor, Node& start) {
  47.     vector<int> dist((MAX_FLOOR + 1) * MAX_ELEVATORS, INT_MAX);
  48.     priority_queue<Node, vector<Node>, NodeComparator> pq;
  49.  
  50.     pq.push(start);
  51.     dist[start.floor * MAX_ELEVATORS + start.elevator] = 0;
  52.  
  53.     while (!pq.empty()) {
  54.         Node u = pq.top();
  55.         pq.pop();
  56.  
  57.         int uIndex = u.floor * MAX_ELEVATORS + u.elevator;
  58.  
  59.         for (Node v : graph[uIndex]) {
  60.            
  61.             int alt = dist[uIndex] + u.dist(v);
  62.             int vIndex = v.floor * MAX_ELEVATORS + v.elevator;
  63.             if (alt < dist[vIndex]) {
  64.                 dist[vIndex] = alt;
  65.                 pq.push(v);
  66.             }
  67.         }
  68.     }
  69.  
  70.     int minDist = INT_MAX;
  71.     for (int i = 0; i < n; i++) {
  72.         minDist = min(minDist, dist[floor * MAX_ELEVATORS + i]);
  73.     }
  74.  
  75.     return minDist;
  76. }
  77.  
  78. int elevatorIn0(vector<vector<int>>& elevators) {
  79.     for (int i = 0; i < elevators.size(); i++) {
  80.         if (elevators[i][0] == 0) {
  81.             return i;
  82.         }
  83.     }
  84.     return -1;
  85. }
  86.  
  87. Graph buildGraph(vector<vector<int>>& elevators, int n, vector<int> T) {
  88.     Graph graph((MAX_FLOOR + 1) * MAX_ELEVATORS);
  89.  
  90.     for (int i = 0; i < n; i++) {
  91.         for (int j = 0; j < elevators[i].size(); j++) {
  92.             // Add same elevator connections
  93.             for (int k = j + 1; k < elevators[i].size(); k++) {
  94.                 Node a(elevators[i][k], i, T[i]);
  95.                 Node b(elevators[i][j], i, T[i]);
  96.                
  97.                 graph[elevators[i][j] * MAX_ELEVATORS + i].push_back(a);
  98.                 graph[elevators[i][k] * MAX_ELEVATORS + i].push_back(b);
  99.             }
  100.  
  101.             // Add same floor connections
  102.             for (int k = 0; k < n; k++) {
  103.                 for (int l = 0; l < elevators[k].size(); l++) {
  104.                     if (elevators[i][j] == elevators[k][l] && k != i) {
  105.                         Node a(elevators[k][l], k, T[k]);
  106.                         Node b(elevators[i][j], i, T[i]);
  107.  
  108.                         graph[elevators[i][j] * MAX_ELEVATORS + i].push_back(a);
  109.                         graph[elevators[k][l] * MAX_ELEVATORS + k].push_back(b);
  110.                     }
  111.                 }
  112.             }
  113.         }
  114.     }
  115.  
  116.     return graph;
  117. }
  118.  
  119. int main() {
  120.     string line;
  121.  
  122.     while (getline(cin, line)) {
  123.         if (line.empty()) {
  124.             break;
  125.         }
  126.         istringstream ssnk(line);
  127.         int n, k;
  128.         ssnk >> n >> k;
  129.        
  130.         getline(cin, line);
  131.  
  132.         istringstream sst(line);
  133.         vector<int> T(n);
  134.        
  135.         int T_i;
  136.         for (int i = 0; i < n; ++i) {
  137.             sst >> T_i;
  138.             T[i] = T_i;
  139.         }
  140.        
  141.         vector<vector<int>> elevators(n);
  142.  
  143.         for (int i = 0; i < n; ++i) {
  144.             int current_floor;
  145.             getline(cin, line);
  146.             if (line.empty()) {
  147.                 getline(cin, line);
  148.             }
  149.  
  150.             istringstream sselv(line);
  151.            
  152.             while (sselv >> current_floor) {
  153.                 elevators[i].push_back(current_floor);
  154.             }
  155.         }
  156.        
  157.         int startIdx = elevatorIn0(elevators);
  158.         if (startIdx == -1) {
  159.             cout << "IMPOSSIBLE" << endl;
  160.             continue;
  161.         }
  162.         Node start(0, startIdx, T[startIdx]);
  163.  
  164.         Graph graph = buildGraph(elevators, n, T);
  165.  
  166.         int result = dijkstra(graph, n, k, start);
  167.  
  168.         if (result == INT_MAX) {
  169.             cout << "IMPOSSIBLE" << endl;
  170.         } else {
  171.             cout << result << endl;
  172.         }
  173.        
  174.     }
  175.  
  176.     return 0;
  177. }
  178.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement