Yiner的ACM

成长的痕迹
<2011年5月>
日一二三四五六
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

统计

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


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