1489: 数字排列

http://www.acmore.net/problem.php?id=1489

Time Limit: 1 Sec  

Memory Limit: 128 MB

Submit: 213  

Solved: 77

Description

 

小Y得到了一个数，他认为相邻位上的数字与数字之间会产生不良影响，比如123,1和2之间产生一个不良影响值，2和3之间产生一个不良影响值。现在他想调整这个数每位的数字的顺序，使得最终得到的数的总的不良影响值最小，且没有前导0。

 

 

Input

 

输入数据的第一行为T表示有T组数据。每组数据先输入一个整数n(0<n<1000000000)，接下来输入10*10的矩阵，Aij表示数字i与数字j相邻产生的不良影响值，0<Aij<1000000，矩阵是对称的，Aij与Aji相等。

 

 

Output

 

对于每组数据输出一行一个数，表示最小的不良影响值。

 

 

Sample Input

 

1

123

0 0 0 0 0 0 0 0 0 0

0 0 10 1 0 0 0 0 0 0

0 10 0 2 0 0 0 0 0 0

0 1 2 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

 

Sample Output

 

3

 

HINT

 

 

 

Source

 

 

 

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int INF=0x3f3f3f3f;int a[15],b[15],vis[15],val[15][15];int len,ans;void DFS(int loc,int sum){    if(sum>ans)        return ;    if(loc==len){        if(ans>sum)            ans=sum;        return ;    }    for(int i=0;i