Advertisement
Guest User

Untitled

a guest
Apr 25th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.45 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define FRU freopen("out.txt","w",stdout)
  3. #define FRO freopen("in.txt","r",stdin)
  4. #define pb push_back
  5. #define mp make_pair
  6. #define ff first
  7. #define ss second
  8. #define mem(ara,n) memset(ara,n,sizeof ara)
  9. #define loop(i,j,n) for(i=j;i<n;i++)
  10. #define rloop(i,j,n) for(i=n;i>=j;i--)
  11. #define INF 2147483647
  12. #define ll long long
  13. #define pii pair<int,int>
  14. #define eps 1e-9
  15. #define mii map<int,int>
  16. #define vi vector<int>
  17. #define all(n) n.begin(),n.end()
  18. #define inf INF
  19. #define INFLL 10000000000000000LL
  20.  
  21. //const int row[]={-1, -1, -1, 0, 0, 1, 1, 1}; // Kings Move
  22. //const int col[]={-1, 0, 1, -1, 1, -1, 0, 1}; // Kings Move
  23. //const int row[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
  24. //const int col[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
  25. //const int row[]={-1,0,0,1,0};
  26. //const int col[]={0,-1,1,0,0};
  27. int gcd(int a,int b)
  28. {
  29. return b==0?a:gcd(b,a%b);
  30. }
  31. int lcm(int a,int b)
  32. {
  33. return ((a*b)/gcd(a,b));
  34. }
  35.  
  36. bool bitcheck(int n,int pos)
  37. {
  38. return (bool)(n & (1<<pos));
  39. }
  40.  
  41. int biton(int n,int pos)
  42. {
  43. return n=n | (1<<pos);
  44. }
  45. int bitoff(int n,int pos)
  46. {
  47. return n=n & ~(1<<pos);
  48. }
  49.  
  50. using namespace std;
  51. struct data
  52. {
  53. int x,y;
  54. int s;
  55. }shop[101];
  56.  
  57. int n,k;
  58. double dp[1<<13][37];
  59.  
  60. double ed(data a,data b)
  61. {
  62. double x=double(a.x-b.x);
  63. double y=double(a.y-b.y);
  64. return sqrt(x*x+y*y);
  65. }
  66. vi ans;
  67. double f(int mask,int ps)
  68. {
  69. if(dp[mask][ps]-(-1)<eps)return dp[mask][ps];
  70. if(mask==(1<<k)-1){return ed(shop[0],shop[ps]);}
  71.  
  72. double ret=10000000.0;
  73. for(int i=1;i<=n;i++)
  74. {if(i==ps)continue;
  75. int j,tmp=mask;
  76. tmp=(mask|shop[i].s);
  77. if(tmp!=mask)
  78. {
  79. double dd=ed(shop[ps],shop[i]);
  80. ret=min(ret,dd+f(tmp,i));
  81. }
  82. }
  83. return dp[mask][ps]=ret;
  84. }
  85.  
  86. int main()
  87. {
  88. //FRO;
  89. //FRU;
  90. //std::ios_base::sync_with_stdio(false);
  91. int a,b,c,i,j,tc,t;
  92. int m,cnt=0;
  93. cin>>tc;
  94. for(t=1;t<=tc;t++)
  95. {
  96. scanf("%d%d",&n,&k);
  97. string s;
  98. shop[0].x=shop[0].y=0;
  99. for(i=1;i<=n;i++)
  100. {
  101. cin>>a>>b;
  102. shop[i].x=a;
  103. shop[i].y=b;
  104. }
  105. for(i=1;i<=n;i++)
  106. {
  107. cin>>s;
  108. a=0;
  109. for(j=0;j<k;j++)if(s[j]=='1')a=biton(a,j);
  110. shop[i].s=a;
  111. }
  112. mem(dp,-1);
  113. printf("%.10f\n",f(0,0));
  114. }
  115. return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement