1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 #define INF 0x3f3f3f3f 7 int n,d[1005],dp[1005][1005]; 8 int dis(int a,int b) 9 {10     int tmp=abs(d[a]-d[b]);11     return min(tmp,360-tmp);12 }13 int TSP_Dp()14 {15     dp[2][1]=dis(1,2);16     for (int i = 3; i <= n + 1; i++) {17         dp[i][i-1] = INF;18 19         for (int j = 1; j < i-1; j++) {20             dp[i][i-1] = min(dp[i][i-1], dp[i-1][j] + dis(i, j));21             dp[i][j] = dp[i-1][j] + dis(i, i-1);22         }23     }24 25     int ans = INF;26     for (int i = 1; i <= n; i++)27         ans = min(ans, dp[n+1][i] + dis(n+1, i));28     return ans;29 }30 int main()31 {32     int t;33     scanf("%d",&t);34     while(t--)35     {36         d[1]=0;37         int ans=0;38         scanf("%d",&n);39         for(int i=2;i<=n+1;i++)40         {41             int a;42             scanf("%d%d",&a,&d[i]);43             if(i==n+1)ans+=a*800;44             ans+=10;45         }46         ans+=TSP_Dp();47         printf("%d\n",ans);48     }49 }