这是水题:
#include<iostream> #include<stdio.h> #include<string.h> using namespace std; int main() { int map[101][101]; int T; int index,i,j; index=1; scanf( "%d",&T ); while( T-- ) { int n; memset( map,0,sizeof(map) ); scanf( "%d",&n ); for( i=1;i<=n;i++ ) for( j=1;j<=n;j++ ) scanf( "%d",&map[i][j] ); int k; int e=n*n-n; bool fax=false; 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 ) { if( map[i][j]>map[i][k]+map[k][j] ) { fax=true; goto ret; } if( map[i][j]==map[i][k]+map[k][j] ) { e--; break; } } } } ret: if( fax ) printf( "Case %d: impossible\n",index++ ); else printf( "Case %d: %d\n",index++,e ); } return 0; }