SHARE
TWEET

Untitled

a guest Sep 16th, 2019 82 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define TRACE(x) x
  6. #define WATCH(x) TRACE( cout << #x" = " << x << endl)
  7. #define PRINT(x) TRACE(printf(x))
  8. #define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl)
  9. #define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end()); } )
  10.  
  11. #define all(v) (v).begin(), (v).end()
  12. #define rall(v) (v).rbegin(), (v).rend()
  13. #define sz(v) (int) (v).size()
  14. #define rep(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
  15. #define pb push_back
  16. #define mp make_pair
  17.  
  18. using ll = long long;
  19. using vi = vector<int>;
  20. using pii = pair<int, int>;
  21. using pll = pair<ll, ll>;
  22.  
  23. constexpr int inf = 0x3f3f3f3f;
  24. constexpr ll MOD = 1000000007LL;
  25. constexpr double tol = 1e-8;
  26.  
  27. void buff() { ios::sync_with_stdio( false ); cin.tie(nullptr); }
  28.  
  29. constexpr int ms = 413;
  30.  
  31. int dp[2][ms][ms][ms];
  32.  
  33. int main()
  34. {
  35.     memset( dp, inf, sizeof(dp) );
  36.    
  37.     buff();
  38.     int n, r;
  39.     cin >> n >> r;
  40.    
  41.     vector< int > t(n);
  42.    
  43.     for(int& x : t) cin >> x;
  44.    
  45.     for(int i = 0; i < r; ++i)
  46.     {
  47.         int a, b, d;
  48.         cin >> a >> b >> d;
  49.         --a, --b;
  50.         dp[1][a][b][0] = dp[0][a][b][0] = min( dp[0][a][b][0], d );
  51.         dp[1][b][a][0] = dp[0][b][a][0] = min( dp[0][b][a][0], d );
  52.     }
  53.    
  54.     for(int i = 0; i < n; ++i) dp[0][i][i][0] = dp[1][i][i][0] = 0;
  55.  
  56.     vector< int > nodes(n, 0); iota(all(nodes), 0 );
  57.     sort( all(nodes), [&] ( const int& a, const int& b ) { return t[a] < t[b]; });
  58.    
  59.     // Tratando empates
  60.     vector< vi > kth_smallest;
  61.     vector< vi > kth_largest;
  62.     vector< int > cur_group = { nodes[0] };
  63.    
  64.     for(int i = 1; i < n; ++i)
  65.     {
  66.         if( t[ nodes[i] ] == t[ nodes[i - 1] ] )
  67.         {
  68.             cur_group.push_back( nodes[i] );
  69.         }
  70.         else
  71.         {
  72.             kth_smallest.push_back( cur_group );
  73.             cur_group.clear();
  74.             cur_group.push_back( nodes[i] );
  75.         }
  76.     }
  77.     kth_smallest.push_back( cur_group );
  78.  
  79.     cur_group.clear();
  80.     cur_group.push_back( nodes[ n - 1] );
  81.    
  82.     for(int i = n - 2; i >= 0; --i)
  83.     {
  84.         if( t[nodes[i]] == t[nodes[i + 1]] )
  85.         {
  86.             cur_group.push_back( nodes[i] );
  87.         }
  88.         else
  89.         {
  90.             kth_largest.push_back( cur_group );
  91.             cur_group.clear();
  92.             cur_group.push_back( nodes[i] );
  93.         }
  94.     }
  95.     kth_largest.push_back( cur_group );
  96.     // Fim do tratamento de empates
  97.  
  98.     for(int z = 0; z < n; ++z)
  99.     {
  100.         for(int x = 0; x < n; ++x)
  101.         {
  102.             for(int y = 0; y < n; ++y)
  103.             {
  104.                 dp[0][x][y][z + 1] = dp[0][x][y][z];
  105.                 dp[1][x][y][z + 1] = dp[1][x][y][z];
  106.             }
  107.         }
  108.        
  109.         for(int x = 0; x < n; ++x)
  110.         {
  111.             for(int y = 0; y < n; ++y)
  112.             {
  113.                 if( z < sz(kth_largest) )
  114.                 {
  115.                     for( int& node : kth_largest[z] )
  116.                     {
  117.                         if( dp[1][x][node][z + 1] != inf && dp[1][node][y][z + 1] != inf )
  118.                         {
  119.                             dp[1][x][y][z + 1] = min( dp[1][x][y][z + 1], dp[1][x][node][z + 1] + dp[1][node][y][z + 1] );
  120.                         }
  121.                     }
  122.                 }
  123.                
  124.                 if( z < sz(kth_smallest) )
  125.                 {
  126.                     for( int& node : kth_smallest[z] )
  127.                     {
  128.                         if( dp[0][x][node][z + 1] != inf && dp[0][node][y][z + 1] != inf )
  129.                         {
  130.                             dp[0][x][y][z + 1] = min( dp[0][x][y][z + 1], dp[0][x][node][z + 1] + dp[0][node][y][z + 1] );
  131.                         }
  132.                     }
  133.                 }
  134.             }
  135.         }
  136.     }
  137.    
  138.     int q;
  139.     cin >> q;
  140.    
  141.     for(int i = 0; i < q; ++i)
  142.     {
  143.         int a, b, k, t;
  144.         cin >> a >> b >> k >> t;
  145.         --a; --b;
  146.         int ans = dp[t][a][b][k];
  147.         cout << ( ans != inf ? ans : -1 ) << '\n';
  148.     }
  149.  
  150.     return 0;
  151. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top