[洛谷U990]传递游戏（90分）

【题目描述 Description】

n个人在做传递物品的游戏,编号为1-n。
游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。
即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；
求当物品经过所有n个人后，整个过程的最小总代价是多少。

 【输入输出格式 Input/output】

【输入格式】
第一行为n,表示共有n个人（16>=n>=2）；
以下为n*n的矩阵，第i+1行、第j列表示物品从编号为i的人传递到编号为j的人所花费的代价，特别的有第i+1行、第i列为-1（因为物品不能自己传给自己），其他数据均为正整数(<=10000)。
【输出格式】
一个数，为最小的代价总和。

【输入输出样例 Sample input/output】

样例测试点#1

输入样例： 

2
-1 9794
2724 –1

输出样例：
2724

【思路】

　　简单的递归深搜回溯，不加最优化剪枝可以过50%的数据，加上最优化剪枝可过90%的数据，剩下10%不知道怎么做了。

var a:array[1..16,1..16] of longint;
    b:array[1..16] of boolean;
    i,n,j:longint;
    minn:longint=maxint;
    sum:longint=0;
    ans:longint;

procedure main(x:longint);
var i:longint;
begin
    if (sum>minn) then exit;
    if (ans=0) then
       if sum<minn then minn:=sum;
    for i:=1 to n do
        if (not b[i])and(a[x,i]<>maxint) then
            begin
                inc(sum,a[x,i]);
                b[i]:=true;
                dec(ans);
                main(i);
                dec(sum,a[x,i]);
                b[i]:=false;
                inc(ans);
            end;
end;

begin
    readln(n);
    for i:=1 to n do
        begin
            for j:=1 to n do
                begin
                    read(a[i,j]);
                    if a[i,j]=-1 then a[i,j]:=maxint;
                 end;
            readln;
        end;
    fillchar(b,sizeof(b),false);
    for i:=1 to n do
        begin
            b[i]:=true;
            ans:=n-1;
            main(i);
            b[i]:=false;
        end;
    writeln(minn);
end.