ismaeil

Unique World

Apr 17th, 2021
649
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// --- Shortest Path + Coin-Change(CC) --- ///
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef pair<int , int> ii;
  7. typedef vector< int > vi;
  8. typedef vector< vi > vvi;
  9. #define PB push_back
  10. #define S second
  11. #define F first
  12. #define OO 1e9
  13.  
  14. const int M = 1e5 + 5e1;
  15. const int N = 5e1 + 2e0;
  16. map<ii ,int> cost;
  17. map<ii , vi> path;
  18. vector< vi > tree;
  19. int memo[N][M];
  20. vi h ,p ,costs;
  21. int n ,m;
  22.  
  23. /// --- Initialization before any test --- ///
  24. void init()
  25. {
  26.     tree.clear();
  27.     cost.clear();
  28.     path.clear();
  29.     costs.clear();
  30.     h.assign(n + 1 ,0);
  31.     p.assign(n + 1 ,1);
  32.     tree.assign(n + 1 ,vi());
  33. }
  34.  
  35. /// --- Return reversed vector --- ///
  36. inline vi reversed(vi a)
  37. {
  38.     reverse(a.begin() ,a.end());
  39.     return a;
  40. }
  41.  
  42. /// --- Calculation height of node and get it's parent  --- ///
  43. void DFS(int u ,int pa ,int H)
  44. {
  45.     h[u] = H;
  46.     p[u] = pa;
  47.     for(int v : tree[u])
  48.         if( v != pa )
  49.             DFS(v ,u ,H + 1);
  50. }
  51.  
  52. /// --- Get path between two nodes using their LCA --- ///
  53. vi getPath(int u ,int v)
  54. {
  55.     vi p1;
  56.     while( h[u] > h[v] )
  57.     {
  58.         p1.PB(u);
  59.         u = p[u];
  60.     }
  61.    
  62.     vi p2;
  63.     while( h[u] < h[v] )
  64.     {
  65.         p2.PB(v);
  66.         v = p[v];
  67.     }
  68.    
  69.     while( u != v )
  70.     {
  71.         p1.PB(u);
  72.         u = p[u];
  73.         p2.PB(v);
  74.         v = p[v];
  75.     }
  76.     p1.PB(u);
  77.    
  78.     vi p3;
  79.     for(int i : p1) p3.PB(i);
  80.     for(int i : reversed(p2)) p3.PB(i);
  81.    
  82.     return p3;
  83. }
  84.  
  85. /// --- Pre-Processing all pathes to use them in DP --- ///
  86. void fillPath()
  87. {
  88.     for(int u = 1 ; u < n ; u++)
  89.         for(int v = u + 1 ; v <= n ; v++)
  90.             path[ ii(u ,v) ] = getPath(u ,v),
  91.             path[ ii(v ,u) ] = getPath(v ,u);
  92. }
  93.  
  94. /// -- XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX -- ///
  95.  
  96. /// --- DP/Coin-Change --- ///
  97. int calc(int i ,int x)
  98. {
  99.     if( i == (int)costs.size() || x <= 0 ) return !x ? 0 : OO;
  100.    
  101.     int &re = memo[i][x];
  102.     if( re + 1 ) return re;
  103.    
  104.     re = OO;
  105.     re = min(re ,calc(i ,x - 2 * costs[i]) + 2);
  106.     re = min(re ,calc(i + 1 ,x));
  107.    
  108.     return re;
  109. }
  110.  
  111. /// --- Get the costes on the path between two nodes (val of coins in CC)--- ///
  112. vi getCosts(int u ,int v)
  113. {
  114.     vi res;
  115.     vi Path = path[ ii(u ,v) ];
  116.    
  117.     for(int i = 0 ; i < (int)Path.size() - 1 ; i++)
  118.     {
  119.         int x = Path[ i ];
  120.         int y = Path[i+1];
  121.         res.PB( cost[ ii(x ,y) ] );
  122.     }
  123.    
  124.     return res;
  125. }
  126.  
  127. /// --- Solve the path like coin-change problem --- ///
  128. void CC(int u ,int v ,int c)
  129. {
  130.     if( u != v )
  131.     {
  132.         int s = (int)(costs = getCosts(u ,v)).size();
  133.        
  134.         int sum = 0;
  135.         for(int i : costs) sum += i;
  136.         costs.pop_back();
  137.        
  138.         memset(memo ,-1 ,sizeof memo);
  139.         int ans = calc(0 ,c - sum) + s;
  140.        
  141.         if( ans < (int)OO )
  142.         {
  143.             printf("Yes %d\n" ,ans);
  144.             return;
  145.         }
  146.         puts("No");
  147.         return;
  148.     }
  149.    
  150.     if( c == 0 )
  151.     {
  152.         printf("Yes %d\n" ,c);
  153.         return;
  154.     }
  155.     puts("No");
  156. }
  157.  
  158. /// -- XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX -- ///
  159.  
  160. /// --- TestCase Solve --- ///
  161. void Solve()
  162. {
  163.     scanf("%d%d" ,&n ,&m);
  164.  
  165.     init();
  166.     for(int i = 0 ; i < m ; i++)
  167.     {
  168.         int u; scanf("%d" ,&u);
  169.         int v; scanf("%d" ,&v);
  170.         int c; scanf("%d" ,&c);
  171.  
  172.         cost[ ii(u ,v) ] = c;
  173.         cost[ ii(v ,u) ] = c;
  174.         tree[u].PB(v);
  175.         tree[v].PB(u);
  176.     }
  177.    
  178.     DFS(1 ,1 ,0);
  179.     fillPath();
  180.    
  181.     int q;
  182.     scanf("%d" ,&q);
  183.     while( q-- )
  184.     {  
  185.         int u; scanf("%d" ,&u);
  186.         int v; scanf("%d" ,&v);
  187.         int c; scanf("%d" ,&c);
  188.         CC(u ,v ,c);
  189.     }
  190. }
  191.  
  192. /// --- Main --- ///
  193. int main()
  194. {
  195.     int Tc;
  196.     scanf("%d" ,&Tc);
  197.    
  198.     while( Tc-- )
  199.     {
  200.         Solve();
  201.         if( Tc ) puts("");
  202.     }
  203. }
  204.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×