fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = 1e9+7;
  5. const int MAXN = 100005;
  6.  
  7. int n, m, Q;
  8. vector<pair<int, int>> adj[MAXN]; // adjacency list: node -> (neighbor, weight)
  9. int s[MAXN], c[MAXN]; // diện tích và chi phí
  10. int dist[MAXN]; // lưu khoảng cách từ node 1
  11.  
  12. // Dijkstra
  13. void dijkstra(int start) {
  14.     fill(dist, dist + n + 1, INF);
  15.     priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
  16.     dist[start] = 0;
  17.     pq.push({0, start});
  18.  
  19.     while (!pq.empty()) {
  20.         auto [d, u] = pq.top(); pq.pop();
  21.         if (d > dist[u]) continue;
  22.         for (auto [v, w] : adj[u]) {
  23.             if (dist[v] > d + w) {
  24.                 dist[v] = d + w;
  25.                 pq.push({dist[v], v});
  26.             }
  27.         }
  28.     }
  29. }
  30.  
  31. struct Hall {
  32.     int area, cost, dist;
  33. };
  34.  
  35. int main() {
  36.     ios::sync_with_stdio(false);
  37.     cin.tie(0);
  38.  
  39.     cin >> n >> m >> Q;
  40.     for (int i = 1; i <= n; ++i) {
  41.         cin >> s[i] >> c[i];
  42.     }
  43.  
  44.     for (int i = 0; i < m; ++i) {
  45.         int u, v, w; cin >> u >> v >> w;
  46.         adj[u].push_back({v, w});
  47.         adj[v].push_back({u, w});
  48.     }
  49.  
  50.     dijkstra(1);
  51.  
  52.     // Tiền xử lý danh sách hội trường hợp lệ
  53.     vector<Hall> halls;
  54.     set<int> areaSet;
  55.  
  56.     for (int i = 1; i <= n; ++i) {
  57.         if (s[i] > 0) {
  58.             halls.push_back({s[i], c[i], dist[i]});
  59.             areaSet.insert(s[i]);
  60.         }
  61.     }
  62.  
  63.     // Nén tọa độ diện tích
  64.     vector<int> areas(areaSet.begin(), areaSet.end());
  65.     int A = areas.size();
  66.  
  67.     // map area -> index
  68.     unordered_map<int, int> areaIndex;
  69.     for (int i = 0; i < A; ++i) {
  70.         areaIndex[areas[i]] = i;
  71.     }
  72.  
  73.     // Với mỗi diện tích đã nén, lưu danh sách (dist, cost), sắp xếp theo dist để binary search
  74.     vector<vector<pair<int,int>>> areaHalls(A); // areaHalls[i] = list of (dist, cost)
  75.  
  76.     for (auto &h : halls) {
  77.         int idx = areaIndex[h.area];
  78.         areaHalls[idx].push_back({h.dist, h.cost});
  79.     }
  80.  
  81.     // Sort theo dist tăng dần, để binary search theo r
  82.     for (int i = 0; i < A; ++i) {
  83.         sort(areaHalls[i].begin(), areaHalls[i].end());
  84.     }
  85.  
  86.     // Xử lý từng truy vấn
  87.     while (Q--) {
  88.         int L, H, r; cin >> L >> H >> r;
  89.         // tìm index trái và phải trong diện tích
  90.         int l = lower_bound(areas.begin(), areas.end(), L) - areas.begin();
  91.         int h = upper_bound(areas.begin(), areas.end(), H) - areas.begin() - 1;
  92.         int res = INF;
  93.         for (int i = l; i <= h; ++i) {
  94.             // tìm cost nhỏ nhất với dist <= r
  95.             auto &vec = areaHalls[i];
  96.             auto it = upper_bound(vec.begin(), vec.end(), make_pair(r, INF));
  97.             for (auto itr = vec.begin(); itr != it; ++itr) {
  98.                 res = min(res, itr->second);
  99.             }
  100.         }
  101.  
  102.         cout << (res == INF ? -1 : res) << '\n';
  103.     }
  104.  
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 7000KB
comments (?)
stdin
copy 
6 6 5
4 9
1 8
3 9
0 0
6 2
3 1
1 2 2
2 3 3
1 4 1
4 5 1
5 3 2
2 6 4
1 3 4
3 6 2
3 6 6
3 6 1
5 5 6
stdout
copy 
8
2
1
9
-1
https://ideone.com/CvxQAW
language:
C++14 (gcc 8.3)
created:
11 days 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!