fork download 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 123
  12. #define MAX 1037471823
  13.  
  14. using namespace std;
  15.  
  16. struct node
  17. {
  18.     int x, y, z;
  19.     bool operator < (const node &k) const { return x < k.x; }
  20. } c[1234];
  21. int t, n, s, K, e, k[MS], vv, v[MS*2], d[MS], x, y, z, a, dp[MS][MS];
  22. bool r[MS][MS], b[MS], bb[MS];
  23.  
  24. int main()
  25. {
  26.     scanf("%d%d%d%d", &t, &n ,&K, &e);
  27.     rep(i, 1, e) scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].z);
  28.     rep(i, 1, e) c[i+e].x = c[i].y, c[i+e].y = c[i].x, c[i+e].z = c[i].z; e *= 2;
  29.     sort(c+1, c+1+e); c[e+1].x = MAX;
  30.     k[1] = 1; rep(i, 2, n+1) { k[i] = k[i-1]; while (c[k[i]].x < i) k[i]++; }
  31.     scanf("%d", &a);
  32.     rep(i, 1, a) 
  33.     {
  34.         scanf("%d%d%d", &z, &x, &y);
  35.         rep(i, x, y) r[z][i] = true;
  36.     }
  37.     rep(s, 1, t) 
  38.     {
  39.         rep(i, 1, n) bb[i] = true;
  40.         rep(i, s, t) 
  41.         {
  42.             rep(j, 1, n) if (r[j][i]) bb[j] = false;
  43.             v[1] = 1; vv = 1;
  44.             rep(j, 1, n) d[j] = MAX; d[1] = 0; b[1] = true;
  45.             while (vv > 0)
  46.             {
  47.                 x = v[1];
  48.                 rep(j, k[x], k[x+1]-1) if (bb[c[j].y] && d[c[j].y] > d[x] + c[j].z)
  49.                 {
  50.                     d[c[j].y] = d[x] + c[j].z;
  51.                     if (b[c[j].y] == false) b[c[j].y] = true, v[++vv] = c[j].y; 
  52.                 } 
  53.                 v[1] = v[vv--]; b[x] = false;
  54.             }
  55.             if (d[n] == MAX) dp[s][i] = MAX; else dp[s][i] = d[n] * (i-s+1);
  56.         }
  57.     }
  58.     rep(i, 0, t-1) rep(j, 1, t-i) rep(o, j, j+i-1) if (dp[j][j+i] > dp[j][o] + dp[o+1][j+i] + K) dp[j][j+i] = dp[j][o] + dp[o+1][j+i] + K;
  59.     printf("%d\n", dp[1][t]);
  60.     return 0;
  61. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin 
5 5 10 8
1 2 1
1 3 3
1 4 2
2 3 2
2 4 4
3 4 1
3 5 2
4 5 2
4
2 2 3
3 1 1
3 3 3
4 4 5
stdout 
32
https://ideone.com/AL34ea
BZOJ 1003
language:
C++ (gcc 8.3)
created:
10 years 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!