Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define FRU freopen("out.txt","w",stdout)
- #define FRO freopen("in.txt","r",stdin)
- #define pb push_back
- #define mp make_pair
- #define ff first
- #define ss second
- #define mem(ara,n) memset(ara,n,sizeof ara)
- #define loop(i,j,n) for(i=j;i<n;i++)
- #define rloop(i,j,n) for(i=n;i>=j;i--)
- #define INF 2147483647
- #define ll long long
- #define pii pair<int,int>
- #define eps 1e-9
- #define mii map<int,int>
- #define vi vector<int>
- #define all(n) n.begin(),n.end()
- #define inf INF
- #define INFLL 10000000000000000LL
- //const int row[]={-1, -1, -1, 0, 0, 1, 1, 1}; // Kings Move
- //const int col[]={-1, 0, 1, -1, 1, -1, 0, 1}; // Kings Move
- //const int row[]={-2, -2, -1, -1, 1, 1, 2, 2}; // Knights Move
- //const int col[]={-1, 1, -2, 2, -2, 2, -1, 1}; // Knights Move
- //const int row[]={-1,0,0,1,0};
- //const int col[]={0,-1,1,0,0};
- int gcd(int a,int b)
- {
- return b==0?a:gcd(b,a%b);
- }
- int lcm(int a,int b)
- {
- return ((a*b)/gcd(a,b));
- }
- bool bitcheck(int n,int pos)
- {
- return (bool)(n & (1<<pos));
- }
- int biton(int n,int pos)
- {
- return n=n | (1<<pos);
- }
- int bitoff(int n,int pos)
- {
- return n=n & ~(1<<pos);
- }
- using namespace std;
- struct data
- {
- int x,y;
- int s;
- }shop[101];
- int n,k;
- double dp[1<<13][37];
- double ed(data a,data b)
- {
- double x=double(a.x-b.x);
- double y=double(a.y-b.y);
- return sqrt(x*x+y*y);
- }
- vi ans;
- double f(int mask,int ps)
- {
- if(dp[mask][ps]-(-1)<eps)return dp[mask][ps];
- if(mask==(1<<k)-1){return ed(shop[0],shop[ps]);}
- double ret=10000000.0;
- for(int i=1;i<=n;i++)
- {if(i==ps)continue;
- int j,tmp=mask;
- tmp=(mask|shop[i].s);
- if(tmp!=mask)
- {
- double dd=ed(shop[ps],shop[i]);
- ret=min(ret,dd+f(tmp,i));
- }
- }
- return dp[mask][ps]=ret;
- }
- int main()
- {
- //FRO;
- //FRU;
- //std::ios_base::sync_with_stdio(false);
- int a,b,c,i,j,tc,t;
- int m,cnt=0;
- cin>>tc;
- for(t=1;t<=tc;t++)
- {
- scanf("%d%d",&n,&k);
- string s;
- shop[0].x=shop[0].y=0;
- for(i=1;i<=n;i++)
- {
- cin>>a>>b;
- shop[i].x=a;
- shop[i].y=b;
- }
- for(i=1;i<=n;i++)
- {
- cin>>s;
- a=0;
- for(j=0;j<k;j++)if(s[j]=='1')a=biton(a,j);
- shop[i].s=a;
- }
- mem(dp,-1);
- printf("%.10f\n",f(0,0));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement