My Pastes
Public Pastes
Layout Width
Share Pastebin
Guest
Public paste!

Untitled

By: a guest | Mar 21st, 2010 | Syntax: C++ | Size: 2.22 KB | Hits: 72 | Expires: Never
Download | Raw | Embed | Report abuse
Copy text to clipboard
  1. #include <cstdio>
  2. #include <algorithm>
  3.  
  4. using namespace std;
  5.  
  6. typedef long long llint;
  7.  
  8. const int MAXN = 102;
  9. const int MAXK = 1002;
  10. const llint inf = 10000000000000000LL;
  11.  
  12. int n;
  13. llint T;
  14.  
  15. int vrsta[MAXK];
  16. int vrijeme[MAXK];
  17.  
  18. llint graf[MAXN][MAXN];
  19. llint mat[60][MAXN][MAXN];
  20. llint tmp[MAXN][MAXN];
  21.  
  22. llint used[MAXN][MAXN];
  23. llint nova[MAXN][MAXN];
  24.  
  25. void mult( llint A[MAXN][MAXN], llint B[MAXN][MAXN] ) {
  26.   for( int i = 0; i < n; ++i )
  27.     for( int j = 0; j < n; ++j )
  28.       tmp[i][j] = inf;
  29.  
  30.   for( int i = 0; i < n; ++i )
  31.     for( int j = 0; j < n; ++j )
  32.       for( int k = 0; k < n; ++k )
  33.         if( A[i][k] + B[k][j] < tmp[i][j] )
  34.           tmp[i][j] = A[i][k] + B[k][j];
  35.  
  36.   for( int i = 0; i < n; ++i )
  37.     for( int j = 0; j < n; ++j )
  38.       A[i][j] = tmp[i][j];
  39. }
  40.  
  41. int main( void ) {
  42.   scanf( "%d %lld", &n, &T );
  43.  
  44.   for( int i = 0; i < n; ++i )
  45.     for( int j = 0; j < n; ++j )
  46.       graf[i][j] = inf;
  47.  
  48.   for( int i = 0; i < n; ++i ) {
  49.     int k, y; scanf( "%d %d", &k, &y );
  50.  
  51.     for( int j = 0; j < k; ++j ) scanf( "%d", &vrsta[j] );
  52.     for( int j = 0; j < k; ++j ) scanf( "%d", &vrijeme[j] );
  53.  
  54.     for( int j = 0; j < k; ++j ) {
  55.       int x = vrsta[j]-1;
  56.       llint w = vrijeme[j]+y;
  57.       if( w < graf[i][x] ) graf[i][x] = w;
  58.     }
  59.   }
  60.  
  61.   for( int i = 0; i < n; ++i )
  62.     for( int j = 0; j < n; ++j )
  63.       mat[0][i][j] = graf[i][j];
  64.  
  65.   for( int k = 1; k < 55; ++k ) {
  66.     for( int i = 0; i < n; ++i )
  67.       for( int j = 0; j < n; ++j )
  68.         mat[k][i][j] = mat[k-1][i][j];
  69.     mult( mat[k], mat[k-1] );
  70.   }
  71.  
  72.   for( int i = 0; i < n; ++i ) {
  73.     for( int j = 0; j < n; ++j )
  74.       used[i][j] = inf;
  75.     used[i][i] = 0;
  76.   }
  77.  
  78.   llint ans = 0;
  79.   for( int t = 54; t >= 0; --t ) {
  80.     for( int i = 0; i < n; ++i )
  81.       for( int j = 0; j < n; ++j )
  82.         nova[i][j] = used[i][j];
  83.     mult( nova, mat[t] );
  84.  
  85.     bool ok = false;
  86.     for( int i = 0; i < n; ++i )
  87.       for( int j = 0; j < n; ++j )
  88.         if( nova[i][j] <= T ) ok = true;
  89.  
  90.     if( ok ) {
  91.       ans |= 1LL<<t;
  92.       for( int i = 0; i < n; ++i )
  93.         for( int j = 0; j < n; ++j )
  94.           used[i][j] = nova[i][j];
  95.     }
  96.   }
  97.  
  98.   printf( "%lld\n", ans );
  99.   return 0;
  100. }
create new paste | create new version of this paste RAW Paste Data