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;
}