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