我加了一个剪枝：
如果在第N步时所走的路程已经超过最小值了，或走了M步(1<=M<=N)后所走的路程已经超过(最小值-(N - M))，就可以放弃这条路了。

可是加了这个剪枝以后，最后一组数据还是超时了（2.5s左右），前面9组都对。
这组数据是这样的：
13
 0 88 99 13 14 15 16 55 16 52 13 19 1
22 0  44 55 66 96 36 66 66 54 88 99 2
51 52 0  53 54 55 66 75 72 74 73 72 3
54 32 13  0 44 55 66 22 88 77 34 33 4
38 26 38 45 0  58 68 72 75 65 85 11 5
18 12 13 14 15 0  16 25 14 35 52 21 6
71 22 33 45 55 65 0  18 29 87 96 45 7
92 92 26 18 19 21 28 0  18 55 36 32 7
45 56 78 65 65 68 63 62 0  69 69 65 6
32 54 56 69 99 22 33 44 55 0  66 77 6
58 58 59 59 65 65 67 67 63 35 0  58 5
55 66 33 22 44 18 59 69 69 65 63 0  4
12 13 18 19 20 11 18 68 59 38 30 15 0

请问大家还有没有其它的剪枝？

还有，顺便发一下我的代码：
VAR
   a: ARRAY[1..40, 1..40] OF INTEGER;
   b: ARRAY[1..40] OF BOOLEAN;
   n: INTEGER;
   minr: LONGINT;
PROCEDURE inputfile;
VAR
   fi: TEXT;
   i, j: INTEGER;
BEGIN
    ASSIGN(fi, 'E1_8.in');
    RESET(fi);
    READ(fi, n);
    FOR i:=1 TO n DO
        FOR j:=1 TO n DO READ(fi, a[i, j]);
    CLOSE(fi);
END;
PROCEDURE xxx(ii, k: INTEGER; r: LONGINT);
VAR
   i: INTEGER;
BEGIN
    IF ii = n THEN
       IF r + a[k, 1] < minr THEN minr := r + a[k, 1];
    IF ii < n THEN BEGIN
       IF r < minr - (n - ii + 1) THEN
          FOR i:=2 TO n DO
              IF b[i] THEN BEGIN
                 b[i] := FALSE;
                 xxx(ii + 1, i, r + a[k, i]);
                 b[i] := TRUE;
              END;
    END;
END;
PROCEDURE printfile;
VAR
   fo: TEXT;
BEGIN
    ASSIGN(fo, 'E1_8.out');
    REWRITE(fo);
    WRITE(fo, minr);
    CLOSE(fo);
END;
BEGIN
    inputfile;
    FILLCHAR(b, SIZEOF(b), TRUE);
    minr := MAXLONGINT;
    xxx(1, 1, 0);
    printfile;
END.

试一下这种优化：

当搜索到：
A→B→C→D
A→C→B→D
这两条时，路径长的直接剪掉

如果实在不行，还可以用搜索的终极绝招：卡时