Advertisement
Guest User

Untitled

a guest
Jan 12th, 2025
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.75 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using vll = vector<ll>;
  5. using pll = pair<ll,ll>;
  6.  
  7. const int maxn=8;
  8.  
  9. struct cube {
  10. ll a,b,c,d,e,f;
  11. cube() : a(0), b(0), c(0), d(0), e(0), f(0) {}
  12. cube(ll _a, ll _b, ll _c, ll _d, ll _e, ll _f) :
  13. a(_a), b(_b), c(_c), d(_d), e(_e), f(_f) {}
  14.  
  15. bool operator < (const cube& other) const {
  16. if (a!=other.a) return a<other.a;
  17. if (b!=other.b) return b<other.b;
  18. if (c!=other.c) return c<other.c;
  19. if (d!=other.d) return d<other.d;
  20. if (e!=other.e) return e<other.e;
  21. if (f!=other.e) return f<other.f;
  22. return false;
  23. }
  24.  
  25. cube colplus() {
  26. return {a,b,f,c,d,e};
  27. }
  28.  
  29. cube colminus() {
  30. return {a,b,d,e,f,c};
  31. }
  32.  
  33. cube rowminus() {
  34. return {c,e,b,d,a,f};
  35. }
  36.  
  37. cube rowplus() {
  38. return {e,c,a,d,b,f};
  39. }
  40. };
  41.  
  42. map<cube,ll> dp[8][8];
  43.  
  44. using node = pair<pll,cube>;
  45. map<cube,node> pr[8][8];
  46. void dijkstra(ll ii, ll jj, cube c) {
  47. set<pair<ll,node>> st;
  48. dp[ii][jj][c] = c.e;
  49. pr[ii][jj][c] = {{ii,jj}, c};
  50. st.insert({c.e, {{ii,jj}, c}});
  51.  
  52. // stop using c, i, j;
  53. while (!st.empty()) {
  54. pair<ll,node> item = *st.begin();
  55. st.erase(st.begin());
  56. pll p = item.second.first;
  57. ll d = item.first;
  58. c = item.second.second;
  59.  
  60. if (dp[p.first][p.second][c] < d) continue;
  61. node thisnode = {p, c};
  62.  
  63. node nextnode;
  64. cube c_next = c.colplus();
  65. nextnode.first.first = p.first;
  66. nextnode.first.second = p.second+1;
  67. nextnode.second = c_next;
  68. if (p.second < 7) { /////
  69. map<cube,ll> &mp = dp[p.first][p.second+1];
  70. if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
  71. mp[c_next] = d + c_next.e;
  72. pr[p.first][p.second+1][c_next] = thisnode;
  73. st.insert({d+c_next.e,nextnode});
  74. }
  75. }
  76.  
  77. c_next = c.colminus();
  78. nextnode.first.first = p.first;
  79. nextnode.first.second = p.second-1;
  80. nextnode.second = c_next;
  81. if (p.second > 0) { /////
  82. auto &mp = dp[p.first][p.second-1];
  83. if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
  84. mp[c_next] = d + c_next.e;
  85. pr[p.first][p.second-1][c_next] = thisnode;
  86. st.insert({d+c_next.e,nextnode});
  87. }
  88. }
  89.  
  90. c_next = c.rowplus();
  91. nextnode.first.first = p.first+1;
  92. nextnode.first.second = p.second;
  93. nextnode.second = c_next;
  94. if (p.first < 7) { /////
  95. auto &mp = dp[p.first+1][p.second];
  96. if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
  97. mp[c_next] = d + c_next.e;
  98. pr[p.first+1][p.second][c_next] = thisnode;
  99. st.insert({d+c_next.e,nextnode});
  100. }
  101. }
  102.  
  103. c_next = c.rowminus();
  104. nextnode.first.first = p.first-1;
  105. nextnode.first.second = p.second;
  106. nextnode.second = c_next;
  107. if (p.first > 0) { /////
  108. auto &mp = dp[p.first-1][p.second];
  109. if (mp.find(c_next) == mp.end() || mp[c_next] > d + c_next.e) {
  110. mp[c_next] = d + c_next.e;
  111. pr[p.first-1][p.second][c_next] = thisnode;
  112. st.insert({d+c_next.e,nextnode});
  113. }
  114. }
  115. }
  116. }
  117.  
  118. vector<string> tr(vector<pll>& vl) {
  119. vector<string> ans;
  120. for (pll p: vl) {
  121. char r = p.first + '1';
  122. char c = p.second + 'a';
  123. string s; s.push_back(c); s.push_back(r);
  124. ans.push_back(s);
  125. }
  126. return ans;
  127. }
  128.  
  129. int main() {
  130. ios::sync_with_stdio(0);
  131. cin.tie(0);
  132. pll x,y; ll a,b,c,d,e,f;
  133. char cb;
  134. char ce;
  135. cin >> cb >> x.first >> ce >> y.first;
  136. cin >> a >> b >> c >> d >> e >> f;
  137. x.first--; y.first--;
  138. x.second = cb - 'a';
  139. y.second = ce - 'a';
  140. cube cc(a,b,c,d,e,f);
  141. dijkstra(x.first, x.second, cc);
  142.  
  143. ll ans = 1e15;
  144. vector<pll> sol;
  145. pll pp;
  146. cube prevc;
  147. for (auto p: dp[y.first][y.second]) {
  148. if (p.second < ans) {
  149. ans = min(p.second, ans);
  150. prevc = p.first;
  151. }
  152. }
  153.  
  154. pp.first = y.first; pp.second = y.second;
  155. while (pp.first != x.first || pp.second != x.second || prevc < cc || cc < prevc) {
  156. sol.push_back(pp);
  157. node myn = pr[pp.first][pp.second][prevc];
  158. prevc = myn.second;
  159. pp = myn.first;
  160. }
  161.  
  162. sol.push_back(pp);
  163. reverse(sol.begin(), sol.end());
  164.  
  165. vector<string> to_print = tr(sol);
  166. cout << ans;
  167. for (string s: to_print) cout << ' ' << s;
  168. cout << '\n';
  169. }
  170.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement