fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int xs, ys, n, dp[1<<24], d[25][25];
  5. array<int, 2> a[24];
  6.  
  7. int sq(int x){return x*x;}
  8.  
  9. int BaoThy(int mask)
  10. {
  11. if(__builtin_popcount(mask)==n) return dp[mask]=0;
  12. if(dp[mask]!=-1) return dp[mask];
  13. int res=2e9;
  14. for (int i=0; i<n; i++){
  15. if(mask&(1<<i)) continue;
  16. res=min(res, BaoThy(mask|(1<<i))+2*d[0][i+1]);
  17. for (int j=i+1; j<n; j++){
  18. if(mask&(1<<j)) continue;
  19. res=min(res, BaoThy(mask|(1<<i)|(1<<j))+d[0][i+1]+d[i+1][j+1]+d[j+1][0]);
  20. }
  21. }
  22. return dp[mask]=res;
  23. }
  24.  
  25. void trace(int mask)
  26. {
  27. if(__builtin_popcount(mask)==n) return;
  28. int res=dp[mask];
  29. for (int i=0; i<n; i++){
  30. if(mask&(1<<i)) continue;
  31. if(res==dp[mask|(1<<i)]+2*d[0][i+1]){
  32. cout << i+1 << " " << 0 << " ";
  33. trace(mask|(1<<i));
  34. return;
  35. }
  36. for (int j=i+1; j<n; j++){
  37. if(mask&(1<<j)) continue;
  38. if(res==dp[mask|(1<<i)|(1<<j)]+d[0][i+1]+d[i+1][j+1]+d[j+1][0]){
  39. cout << i+1 << " " << j+1 << " " << 0 << " ";
  40. trace(mask|(1<<i)|(1<<j));
  41. return;
  42. }
  43. }
  44. }
  45. assert(0);
  46. }
  47.  
  48. void solve()
  49. {
  50. memset(dp, -1, sizeof(dp));
  51. int res=BaoThy(0);
  52. cout << res << "\n" << 0 << " ";
  53. trace(0);
  54. }
  55.  
  56. int main()
  57. {
  58. ios_base::sync_with_stdio(0);
  59. cin.tie(0); cout.tie(0);
  60. freopen("LFO.inp", "r", stdin);
  61. //freopen("LFO.out", "w", stdout);
  62. cin >> xs >> ys >> n;
  63. for (int i=0; i<n; i++){
  64. cin >> a[i][0] >> a[i][1];
  65. int t=sq(a[i][0]-xs)+sq(a[i][1]-ys);
  66. d[i+1][0]=t;
  67. d[0][i+1]=t;
  68. }
  69. for (int i=0; i<n; i++){
  70. for (int j=i+1; j<n; j++){
  71. int t=sq(a[j][0]-a[i][0])+sq(a[j][1]-a[i][1]);
  72. d[i+1][j+1]=t;
  73. d[j+1][i+1]=t;
  74. }
  75. }
  76. solve();
  77. return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 69400KB
stdin
Standard input is empty
stdout
0
0