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