ACMboy
  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜
城市规划

城市规划

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:153            测试通过:46

描述

NanJing准备开发一片荒地，目前已经规划好了一些居民点，还要建设道路。由于经费问题，现在想在保持任意两点间的距离最短的前提下，用尽可能少的经费把这些点连接起来。需要注意的是并不是任意两个居民点间都能直接相连。现在给出两两居民点间的花费，当然了，花费和路径长度成正比~

 

输入

第一行是个N<=100，表示N个居民点。

下面是个N*N的矩阵，第i行第j列，表示i到j的花费，可能有负数，表示两地不相连。保证有解。

 

输出

输出一行为总花费。

 

样例输入

3
0 2 1
2 0 3
1 3 0

样例输出

3

QQ:765391213

  #include <stdio.h>
#include <string.h>
const int MAXN=100;
const int MAXINT=10001;
int n,dis[MAXN][MAXN],flag[MAXN][MAXN];
int main()
{
    scanf("%d",&n);
    int k,i,j,temp;
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            scanf("%d",&dis[i][j]);
            if(dis[i][j]<0)
                dis[i][j]=MAXINT;
        }
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                flag[i][j]=1;
            for(k=0;k<n;k++)
                for(i=0;i<n;i++)
                {
                    if(i==k) continue;
                    for(j=0;j<n;j++)
                    {
                        if(k==j)continue;
                        temp=dis[k][j]+dis[i][k];
                        if(temp<=dis[i][j]){
                            flag[i][j]=0;
                            dis[i][j]=temp;
                        }
                    }
                }
                int ans=0;
                for(i=0;i<n;i++)for(j=i+1;j<n;j++)
                    if(flag[i][j]) ans+=dis[i][j];
                    printf("%d\n",ans);
                    return 0;
}
posted on 2010-04-12 12:19 EG-HUA 阅读(497) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理