Yiner的ACM

成长的痕迹
<2011年3月>
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

统计

  • 随笔 - 29
  • 文章 - 0
  • 评论 - 2
  • 引用 - 0

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

最短路径问题No.1
f
#include<iostream>
#include
<stdio.h>
#include
<cstring>
using namespace std;
#define INF 5000000
int a[201];
int c[201][201];
int d[201][201];

int main()
{
    
int n;
    
int i,j,m,kk,k,p;
    
int max1;

    scanf(
"%d",&n);
    
int l;
    
for(l=1;l<=n;l++)
    
{      memset(a,0,sizeof(a));
           memset(c,
0,sizeof(c));
           memset(d,
0,sizeof(d));
        scanf(
"%d",&m);
        
for( i=0;i<m;i++)
         scanf(
"%d",&a[i]);
         
for(i=0;i<m;i++)
         
for(j=0;j<m;j++)
          
{
              scanf(
"%d",&d[i][j]);
            
if(d[i][j]==-1)
            d[i][j]
=INF;
          }

           max1
=0;
           
for(k=0;k<m;k++)
           
for(i=0;i<m;i++)
           
for(j=0;j<m;j++)
            
{

                
if(d[i][j]>(d[i][k]+d[k][j]))
                d[i][j]
=d[i][k]+d[k][j];
            }

            kk
=0;

        
for(p=0;p<m;p++)
       
{

           
if(p<m-1)
            
{
                max1
+=d[a[p]][a[p+1]];
                
if(d[a[p]][a[p+1]]==INF)
                kk
=1;
            }

            
else
            
{
                max1
+=d[a[p]][a[0]];
                
if(d[a[p]][a[0]]==INF)
                 
{kk=1;}
            }


       }

      
if(kk==1)
        printf(
"impossible\n");
        
else
       printf(
"%d\n",max1);
    }

    
return 0;
}

posted on 2011-05-08 22:07 Yiner 阅读(124) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理