● 1002 - 荔园在线 | 深圳大学学生论坛,荔园晨风BBS,深大在线网站

荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀

发信人: huhaiming (一生只爱她), 信区: Program
标  题: 1002
发信站: 荔园晨风BBS站 (Sun May 25 10:16:49 2003), 站内信件

//这题是关于最短路径和回溯搜索的
//ZOJ Monthly, May 2003 Contest 1002
//Equivalence
#include <stdio.h>
#include <string.h>

bool c[6][6],t[6][6],temp[6][6];
int n,g[6][6],b[6][6],result;

void search(int m,int p)
{
        int i,j,k,x,y;
        if (m==n*n){
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                                temp[i][j]=t[i][j];
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                                for(k=0;k<n;k++)
                                        if (temp[j][i]&&temp[i][k]) temp[j][k]
=1;
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++) if (!temp[i][j]) return;
                if (p<result) result=p;
        }
        if (p>=result) return;
        x=m/n,y=m%n;
        if (x==y||!c[x][y]){
                search(m+1,p);
                return;
        }
        t[x][y]=1;
        search(m+1,p+g[x][y]);
        t[x][y]=0;
        search(m+1,p);
}

int main()
{
        int i,j,k;
        freopen("1002.in","r",stdin);
        while(scanf("%d",&n)!=EOF){
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++){
                                scanf("%d",&g[i][j]);
                                b[i][j]=g[i][j];
                        }
                for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                                for(k=0;k<n;k++)
                                        if (b[j][i]+b[i][k]<b[j][k]) b[j][k]
=b[j][i]+b[i][k];

                for(i=0;i<n;i++)
                        for(j=0;j<n;j++)
                                if (b[i][j]!=g[i][j]) c[i][j]=0;
                                else c[i][j]=1;
                result=0x7fffffff;
                memset(t,0,sizeof(t));
                for(i=0;i<n;i++) t[i][i]=1;
                search(0,0);
                printf("%d\n",result);
        }
        return 0;
}

--

菩提本无树，明镜亦非台

本来无一物，何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]

荔园在线首页友情链接：深圳大学深大招生荔园晨风BBS S-Term软件网络书店