ACMboy

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

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

城市规划

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

描述

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

 

输入

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

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

 

输出

输出一行为总花费。

 

样例输入

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 阅读(458) 评论(0)  编辑 收藏 引用

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