提示: 欢迎访问OurACM平台。
Problem 2120 数字排列

Accept: 146    Submit: 501
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

S得到了一个数,他认为相邻位上的数字与数字之间会产生不良影响,比如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

Source

FOJ有奖月赛-2013年4月(校赛热身赛)

Submit  Back  Status  Discuss