Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 7th, 2012  |  syntax: C++  |  size: 2.42 KB  |  hits: 19  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<string>
  3. #include<cstring>
  4. #include<sstream>
  5. #include<cctype>
  6. #include<string.h>
  7. #include<algorithm>
  8. #include<cmath>
  9. #include<stack>
  10. #include<fstream>
  11. #include<cstdlib>
  12. #include<vector>
  13. #include<map>
  14. #include<utility>
  15. #include<iomanip>
  16. #include<queue>
  17. #define eps 1e-9
  18. #define max(a,b) ((a>b)?a:b)
  19. #define min(a,b) ((a<b)?a:b)
  20. #define pb(a) push_back(a)
  21. #define mp(a,b) make_pair(a,b)
  22. #define pi acos(-1.0)
  23. #define SET(a) memset(a,-1,sizeof a)
  24. #define CLR(a) memset(a,0,sizeof a)
  25. #define inf 2000000000
  26. #define MOD 1000000007
  27.  
  28. using namespace std;
  29.  
  30. struct node
  31.     {
  32.     int x,y;
  33.     };
  34.  
  35. long long dp[16+2][65535+5];
  36. int dis[1000+2][1000+2],res[1000+2][1000+2];
  37. bool vis[1000+2][1000+2];
  38.  
  39. int dx[8]={-1,-2,-2,-1,1,2, 2, 1};
  40. int dy[8]={-2,-1, 1, 2,2,1,-1,-2};
  41.  
  42. int n,k,st,X[16+5],Y[16+5];
  43.  
  44. long long func(int prev,int bit)
  45.     {
  46.     if(bit==((1<<k)-1))
  47.         {
  48.         return dp[prev][bit]=res[abs(X[prev]-X[st])][abs(Y[prev]-Y[st])];
  49.         }
  50.     if(dp[prev][bit]!=-1) return dp[prev][bit];
  51.     long long ret=inf;
  52.     for(int i=0;i<k;i++)
  53.         {
  54.         if((bit&(1<<i))==0)
  55.             {
  56.             ret=min(ret,res[abs(X[prev]-X[i])][abs(Y[prev]-Y[i])]+func(i,bit|(1<<i)));
  57.             }
  58.         }
  59.     return dp[prev][bit]=ret;
  60.     }
  61.  
  62. int main()
  63. {
  64. int t,kk=1;
  65.  
  66.     node N,U,V;
  67.  
  68.     N.x=N.y=1;
  69.  
  70.     vis[N.x][N.y]=1;
  71.  
  72.     queue<node>q;
  73.     q.push(N);
  74.  
  75.     while(!q.empty())
  76.         {
  77.         U=q.front();
  78.         q.pop();
  79.  
  80.         for(int i=0;i<8;i++)
  81.             {
  82.             V.x=U.x+dx[i];
  83.             V.y=U.y+dy[i];
  84.             if(V.x>=1 && V.x<=1000 && V.y>=1 && V.y<=1000 && !vis[V.x][V.y])
  85.                 {
  86.                 vis[V.x][V.y]=1;
  87.                 res[abs(V.x-1)][abs(V.y-1)]=dis[V.x][V.y]=dis[U.x][U.y]+1;
  88.                 q.push(V);
  89.                 }
  90.             }
  91.         }
  92.  
  93. scanf("%d",&t);
  94. while(t--)
  95.     {
  96.     scanf("%d%d",&n,&k);
  97.  
  98.     CLR(X);
  99.     CLR(Y);
  100.  
  101.     for(int i=0;i<k;i++)
  102.         {
  103.         scanf("%d%d",&N.x,&N.y);
  104.         X[i]=N.x;
  105.         Y[i]=N.y;
  106.         }
  107.  
  108.     printf("Case %d: ",kk++);
  109.     if(k==1) {printf("0\n");continue;}
  110.  
  111.     long long ans=inf;
  112.  
  113.     if(n==4) res[3][0]=res[0][3]=5;
  114.     else res[3][0]=res[0][3]=3;
  115.  
  116.     SET(dp);
  117.  
  118.     for(st=0;st<k;st++)
  119.         {
  120.         ans=min(ans,func(st,(1<<st)));
  121.         }
  122.     if(ans==inf) ans=0;
  123.  
  124.     printf("%lld\n",ans);
  125.  
  126.     }
  127. return 0;
  128. }
create a new version of this paste RAW Paste Data