fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. const ll oo = 2e18;
  7. const int B = 100;
  8. const int N = 1e5+5;
  9. const int NODES = 5e5+5;
  10.  
  11. struct Edge {
  12.     int to;
  13.     ll w;
  14. };
  15.  
  16. int n, m, c, S[B], bup[B][N], bdown[B][N];
  17. vector<Edge> adj[NODES];
  18. vector<int> st[B], up[B], down[B];
  19. ll dist[NODES];
  20.  
  21. void solve() {
  22.     cin >> n >> m >> c;
  23.  
  24.     int nodes = n + m;
  25.     for (int d = 1; d < B; d++) {
  26.         int S_d = max(1, (int)sqrt(n / (2.0 * d)));
  27.         S[d] = S_d;
  28.         st[d].assign(d + 1, 0);
  29.         int blocks = 0;
  30.         for (int r = 0; r < d; r++) {
  31.             int cnt = 0;
  32.             for (int x = r; x <= n; x += d)
  33.                 if (x >= 1) cnt++;
  34.             int b = (cnt + S_d - 1) / S_d;
  35.             st[d][r] = blocks;
  36.             blocks += b;
  37.         }
  38.         up[d].resize(blocks);
  39.         down[d].resize(blocks);
  40.         for (int i = 0; i < blocks; i++) {
  41.             up[d][i] = ++nodes;
  42.             down[d][i] = ++nodes;
  43.         }
  44.     }
  45.  
  46.     for (int i = 1; i < n; i++) {
  47.         adj[i].push_back({i + 1, c});
  48.         adj[i + 1].push_back({i, c});
  49.     }
  50.  
  51.     for (int d = 1; d < B; d++) {
  52.         int S_d = S[d];
  53.         for (int x = 1; x <= n; x++) {
  54.             int r = x % d;
  55.             int first = (r == 0 ? d : r);
  56.             int idx = (x - first) / d;
  57.             int b = idx / S_d;
  58.             int bid = st[d][r] + b;
  59.             int u = up[d][bid], v = down[d][bid];
  60.             bup[d][x] = u, bdown[d][x] = v;
  61.             adj[x].push_back({u, 0});
  62.             adj[v].push_back({x, 0});
  63.         }
  64.     }
  65.  
  66.     for (int i = 1; i <= m; i++) {
  67.         int l, d, k, t; cin >> l >> d >> k >> t;
  68.         int R = l + k * d, V = n + i;
  69.         if (d >= B) {
  70.             for (int j = 0; j <= k; j++) {
  71.                 int x = l + j * d;
  72.                 if (x > n) break;
  73.                 adj[x].push_back({V, t});
  74.                 adj[V].push_back({x, 0});
  75.             }
  76.         } else {
  77.             int S_d = S[d];
  78.             int r = l % d;
  79.             int first = (r == 0 ? d : r);
  80.             int idx_s = (l - first) / d, idx_e = (R - first) / d;
  81.             int b_s = idx_s / S_d, b_e = idx_e / S_d;
  82.             if (b_s == b_e) {
  83.                 for (int idx = idx_s; idx <= idx_e; idx++) {
  84.                     int x = first + idx * d;
  85.                     adj[x].push_back({V, t});
  86.                     adj[V].push_back({x, 0});
  87.                 }
  88.             } else {
  89.                 int end_i = (b_s + 1) * S_d - 1;
  90.                 for (int idx = idx_s; idx <= end_i; idx++) {
  91.                     int x = first + idx * d;
  92.                     adj[x].push_back({V, t});
  93.                     adj[V].push_back({x, 0});
  94.                 }
  95.                 for (int b = b_s + 1; b <= b_e - 1; b++) {
  96.                     int u = bup[d][first + b * S_d * d], v = bdown[d][first + b * S_d * d];
  97.                     adj[u].push_back({V, t});
  98.                     adj[V].push_back({v, 0});
  99.                 }
  100.                 int start_i = b_e * S_d;
  101.                 for (int idx = start_i; idx <= idx_e; idx++) {
  102.                     int x = first + idx * d;
  103.                     adj[x].push_back({V, t});
  104.                     adj[V].push_back({x, 0});
  105.                 }
  106.             }
  107.         }
  108.     }
  109.  
  110.     for (int i = 1; i <= nodes; i++) dist[i] = oo;
  111.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
  112.  
  113.     dist[1] = 0;
  114.     pq.push({0, 1});
  115.  
  116.     while (!pq.empty()) {
  117.         auto [d, u] = pq.top(); pq.pop();
  118.         if (d > dist[u]) continue;
  119.  
  120.         for (Edge& e : adj[u]) {
  121.             int v = e.to, w = e.w;
  122.             if (dist[v] > d + w) {
  123.                 dist[v] = d + w;
  124.                 pq.push({dist[v], v});
  125.             }
  126.         }
  127.     }
  128.  
  129.     for (int i = 2; i <= n; i++) {
  130.         if (dist[i] == oo) cout << "-1 ";
  131.         else cout << dist[i] << " ";
  132.     }
  133.     cout << "\n";
  134. }
  135.  
  136.  
  137. int main() {
  138.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  139.  
  140.     int tests = 1; // cin >> tests;
  141.     while (tests--) solve();
  142.  
  143.     #ifndef ONLINE_JUDGE
  144.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  145.     #endif
  146.  
  147.     return 0;
  148. }
Success #stdin #stdout 0.02s 93792KB
comments (?)
stdin
copy 
6 3 10
1 2 2 2
3 1 1 1
2 1 1 1
stdout
copy 
3 2 3 2 12
https://ideone.com/34Un4T
language:
C++14 (gcc 8.3)
created:
3 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!