fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define pii pair<int, int>
  6.  
  7. const int INF = 1e18 + 7;
  8.  
  9. struct Edge {
  10.     int to;
  11.     int cost;
  12. };
  13.  
  14. signed main() {
  15.     // Tối ưu I/O cho C++
  16.     ios_base::sync_with_stdio(false);
  17.     cin.tie(NULL);
  18.  
  19.     int n;
  20.     if (!(cin >> n)) return 0;
  21.  
  22.     vector<int> x(n + 1), A(n + 1);
  23.     for (int i = 1; i <= n; i++) cin >> x[i];
  24.     for (int i = 1; i <= n; i++) cin >> A[i];
  25.  
  26.     vector<vector<int>> port(n + 1);
  27.     vector<int> compress;
  28.     for (int i = 1; i <= n; i++) {
  29.         int k; cin >> k;
  30.         port[i].resize(k);
  31.         for (int j = 0; j < k; j++) {
  32.             cin >> port[i][j];
  33.             compress.push_back(port[i][j]);
  34.         }
  35.     }
  36.  
  37.     // Nén tọa độ cho các loại cổng
  38.     sort(compress.begin(), compress.end());
  39.     compress.erase(unique(compress.begin(), compress.end()), compress.end());
  40.  
  41.     int P = compress.size();
  42.     vector<vector<int>> machines_with_port(P + 1);
  43.  
  44.     for (int i = 1; i <= n; i++) {
  45.         for (int &p : port[i]) {
  46.             p = lower_bound(compress.begin(), compress.end(), p) - compress.begin() + 1;
  47.             machines_with_port[p].push_back(i);
  48.         }
  49.     }
  50.  
  51.     // Tính toán số lượng nút tối đa (N máy thật + 2 * sum(k_i) nút ảo)
  52.     int max_nodes = n;
  53.     for (int p = 1; p <= P; p++) {
  54.         max_nodes += 2 * machines_with_port[p].size();
  55.     }
  56.  
  57.     vector<vector<Edge>> adj(max_nodes + 1);
  58.     int total_nodes = n; // Các nút từ 1 đến N là các máy thật
  59.  
  60.     // Xây dựng các làn đường nút ảo
  61.     for (int p = 1; p <= P; p++) {
  62.         auto &machines = machines_with_port[p];
  63.         int k = machines.size();
  64.         if (k <= 1) continue;
  65.  
  66.         // Sắp xếp các máy có chung cổng theo Base Voltage x[i]
  67.         sort(machines.begin(), machines.end(), [&](int a, int b) {
  68.             return x[a] < x[b];
  69.         });
  70.  
  71.         vector<int> U(k), D(k);
  72.         for (int i = 0; i < k; i++) {
  73.             U[i] = ++total_nodes;
  74.             D[i] = ++total_nodes;
  75.         }
  76.  
  77.         for (int i = 0; i < k; i++) {
  78.             int u = machines[i];
  79.  
  80.             // 1. Máy thật chui vào làn đường (Chi phí 0)
  81.             adj[u].push_back({U[i], 0});
  82.             adj[u].push_back({D[i], 0});
  83.  
  84.             // 2. Đi từ làn đường ra máy thật (Trả chi phí Startup Cost A[u])
  85.             adj[U[i]].push_back({u, A[u]});
  86.             adj[D[i]].push_back({u, A[u]});
  87.  
  88.             // 3. Nối các nút ảo trên làn đường
  89.             if (i < k - 1) { // Làn đi lên (tăng điện áp)
  90.                 int cost = x[machines[i + 1]] - x[machines[i]];
  91.                 adj[U[i]].push_back({U[i + 1], cost});
  92.             }
  93.             if (i > 0) {     // Làn đi xuống (giảm điện áp)
  94.                 int cost = x[machines[i]] - x[machines[i - 1]];
  95.                 adj[D[i]].push_back({D[i - 1], cost});
  96.             }
  97.         }
  98.     }
  99.  
  100.     // Thuật toán Dijkstra tìm đường đi ngắn nhất từ 1 đến N
  101.     vector<int> dist(total_nodes + 1, INF);
  102.     priority_queue<pii, vector<pii>, greater<pii>> pq;
  103.  
  104.     dist[1] = 0;
  105.     pq.push({0, 1});
  106.  
  107.     while (!pq.empty()) {
  108.         auto [d, u] = pq.top();
  109.         pq.pop();
  110.  
  111.         if (d > dist[u]) continue;
  112.         if (u == n) break; // Đã tới đích, dừng sớm để tối ưu thêm
  113.  
  114.         for (auto &edge : adj[u]) {
  115.             int v = edge.to;
  116.             int cost = edge.cost;
  117.             if (dist[v] > dist[u] + cost) {
  118.                 dist[v] = dist[u] + cost;
  119.                 pq.push({dist[v], v});
  120.             }
  121.         }
  122.     }
  123.  
  124.     cout << (dist[n] == INF ? -1 : dist[n]) << "\n";
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5TM4ey
language:
C++14 (gcc 8.3)
created:
22 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!