题意：类似于TSP问题，只是每个点可以走多次，求回到起点的最短距离（起点为点0）。

分析：状态压缩，先预处理各点之间的最短路，然后sum【i】【buff】表示在i点，状态为buff时所耗时。。。。。。。

所以把10 * 1024 种状态来一遍，取sum【0】【（1<<n）-1】的最小值

只是把状态压缩DP改成bfs+状态压缩了

#include <cstdio>

#include <iostream>

#include <cstring>

#include <cmath>

#define INF 0x7FFFFFFF

using namespace std;

int dist[11][11],sum[11][1 << 10];

struct node {

    int x,buff;

} q[55555];

int head,tail,n,ans;

void floyd() {

    for(int i=0; i<=n; i++) {

        for(int j=0; j<=n; j++) {

            for(int k=0; k<=n; k++) {

                if(dist[j][i] + dist[i][k] < dist[j][k]) dist[j][k] = dist[j][i] + dist[i][k];

            }

        }

    }

}

void bfs() {

    ans = INF;

    memset(sum,0,sizeof(sum));

    head = 0;

    tail = 0;

    q[head].x = 0;

    q[head++].buff = 0;

    while(head != tail) {

        node t = q[tail ++];

        node tt;

        if(t.x == 0 && t.buff == (1 << n) - 1) {

            ans = min(ans,sum[t.x][t.buff]);

        }

        for(int i=0; i<=n; i++) {

            if(t.x == i) continue;

            if(i != 0) {

                if(t.buff & (1 << (i-1))) tt.buff = t.buff;

                else tt.buff = t.buff + (1 << (i-1));

            } else tt.buff = t.buff;

            //如果该点该状态已经访问过，而这次如果没有更优解，则剪了

            if(sum[i][tt.buff] != 0 && sum[i][tt.buff] > sum[t.x][t.buff] + dist[t.x][i]) {

                sum[i][tt.buff] = sum[t.x][t.buff] + dist[t.x][i];

                tt.x = i;

                q[head++] = tt;

            //未访问则老样子

            } else if(sum[i][tt.buff] == 0) {

                sum[i][tt.buff] = sum[t.x][t.buff] + dist[t.x][i];

                tt.x = i;

                q[head ++] = tt;

            }

        }

    }

}

int main() {

    while(scanf("%d",&n) && n) {

        for(int i=0; i<=n; i++)

            for(int j=0; j<=n; j++) {

                scanf("%d",&dist[i][j]);

            }

        floyd();

        bfs();

        printf("%d\n",ans);

    }

    return 0;

}