hdu 题目4034 (floyd算法的理解变形)

https://acm.hdu.edu.cn/showproblem.php?pid=4034



/***************************
# 2013-11-11 21:24:17 
# Time: 46MS   Memory: 280K
# Author: zyh
***************************/ 
#define N 105
#include<stdio.h>

int a[N][N];
 
int main()
{
	int tt,t,n,i,j,k,m;
	scanf("%d",&t);
	for(tt=1;tt<=t;tt++){
		m=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				scanf("%d",&a[i][j]);
				if(a[i][j]) m++;
			}
		}
		//floyd算法 
		int flag=1,count=0;  
	    for(i=1;i<=n;i++)  
	        for(j=1;j<=n;j++)  
	        {  
	            if( i==j )continue;  
	            for(k=1;k<=n;k++)  
	            {  
	                if(i==k||j==k || !a[i][k] || !a[k][j])continue;  
	                if(a[i][j]>a[i][k]+a[k][j]) //如果给出的不是i,j之间的最短路径 ,直接退出 
	                { flag = 0;  goto ans; }  //利用goto跳出多重循环 
	                else  if(a[i][j]==a[i][k]+a[k][j])  //有其他路径可以到达,则去掉当前路径 
	                {  
	                    m--;  
	                    break;  
	                }  
	            }  
	        }  
		ans:
			printf("Case %d: ",tt);
			if(!flag) puts("impossible");
			else	printf("%d\n",m);
	}
	return 0; 
}